What does Detours and the Depth of Thinking conclude, in numbers, about “The Limits of Greed: Inside and Outside the Matroid”?
Answer: Chapter 3 sets greed against dynamic programming on matroids and beyond; in the knapsack trap greed obtains 0.0002 of the optimum.
Scope of the numbers: Parameters are illustrative and all calculations are generated by the book's programs. This is not investment advice or advice on any particular business decision, and it promises no return.
Data table
The numbers below are printed verbatim by the chapter's Python program and can be reproduced by running it. standard-library Python onlyprinted values that match the answer: 0.0002
| A. Trap instance: greedy / optimum | |
| budget | 10: greedy 2 optimum 10 ratio 0.2000 |
| budget | 100: greedy 2 optimum 100 ratio 0.0200 |
| budget | 1,000: greedy 2 optimum 1,000 ratio 0.0020 |
| budget 10,000: greedy | 2 optimum 10,000 ratio 0.0002 |
| B. 1,000 random instances (12 items, budget 60) | |
| greedy optimal in 598 (59.8%) | |
| mean ratio 0.9828; 1st percentile 0.8663; worst 0.7410 |
Show the full program
# Chapter 3. p32: greedy by value density on a budget - how bad can it be?
# 0/1 knapsack (not a matroid). Greedy takes items by value per unit of
# budget while they fit; dynamic programming gives the exact optimum.
# Part A: the textbook trap - item 1 (value 2, cost 1) and item 2
# (value C, cost C) under budget C: greedy keeps item 1, then item 2
# no longer fits, so greedy / optimum = 2 / C, unbounded as C grows.
# Part B: 1,000 random instances (12 items, costs 1..30, values 1..60,
# budget 60) - typical rather than worst case. Synthetic data.
import math
import random
def greedy(items, cap):
left, got = cap, 0
for v, c in sorted(items, key=lambda it: (-it[0] / it[1], it[1])):
if c <= left:
left -= c
got += v
return got
def exact(items, cap):
best = [0] * (cap + 1)
for v, c in items:
for b in range(cap, c - 1, -1):
best[b] = max(best[b], best[b - c] + v)
return best[cap]
print("A. Trap instance: greedy / optimum")
for C in (10, 100, 1000, 10000):
items = [(2, 1), (C, C)]
g, o = greedy(items, C), exact(items, C)
print(" budget {:>6,}: greedy {:>3,} optimum {:>6,} ratio {:.4f}"
.format(C, g, o, g / o))
rng = random.Random(38432)
ratios, hit = [], 0
for _ in range(1000):
items = [(rng.randint(1, 60), rng.randint(1, 30)) for _ in range(12)]
g, o = greedy(items, 60), exact(items, 60)
ratios.append(g / o)
hit += g == o
ratios.sort()
print("B. 1,000 random instances (12 items, budget 60)")
print(" greedy optimal in {} ({:.1%})".format(hit, hit / 1000))
print(" mean ratio {:.4f}; 1st percentile {:.4f}; worst {:.4f}".format(
math.fsum(ratios) / 1000, ratios[10], ratios[0]))Single source and citation
Fan, Y. (2026). When the Shortest Path Fails: Brachistochrone Detours, Second-Order Consequence Mapping and Holographic Deep Thinking (Version 1.0.0), Chapter 3: The Limits of Greed: Inside and Outside the Matroid. 5D Library. DOI pending
DOI pending · monograph page goes live after publication · 5DL-B-384 · v1.0.0 · CC-BY-NC-ND-4.0
BibTeX
@book{fan2026384,
author = {Fan, Yafu},
title = {When the Shortest Path Fails: Brachistochrone Detours, Second-Order Consequence Mapping and Holographic Deep Thinking},
year = {2026},
publisher = {5D Library},
edition = {1.0.0},
note = {DOI pending}
}Other chapter answers in this book
- Chapter 1 · The Brachistochrone: Why the Straight Line Loses to the Cycloid
- Chapter 2 · Roundabout Preparation: the Break-even of Building the Road First
- Chapter 4 · One More Road and Everyone Is Slower: Braess's Paradox and Selfish Routing
- Chapter 5 · The Second-Order Interest on First-Order Shortcuts: Hidden Rework Liability
- Chapter 6 · The Optimal Depth of Deliberation: Consequence Trees, Evidence For and Against, and Tail Stress
- Chapter 7 · Classical Sources: the Sunzi on Manoeuvring, the Twenty-Second Chapter of the Laozi, and Bernoulli's Challenge
- Chapter 8 · Closing the Loop: the Holographic Decision Ledger, Field Tools and Checker Specifications