Definition
Unmodified value-density greedy can be arbitrarily bad
For the 0-1 max-value knapsack problem, consider sorting items by decreasing profit-to-weight ratio and taking each item if it fits. For every
, there is a two-item instance with positive integer sizes and values on which the returned value is at most .
Consequently this unmodified greedy algorithm has no positive constant multiplicative approximation guarantee.
Counterexample
A tiny higher-density item blocks the valuable item
Choose an integer scale for the desired ratio
Fix
and set . Give the knapsack capacity and the following two items:
Item Size Value Density All sizes and values are positive integers, and the densities are strictly ordered, so tie-breaking is irrelevant.
Follow the greedy selection
Greedy selects
first because . Only capacity remains, so no longer fits. The returned value is . Both items cannot fit together because
. The second item alone fits and has value , so the optimum is . Make the ratio as small as requested
Since
,
This construction works for every positive, so no fixed positive ratio is guaranteed.
Scope of the counterexample
This concerns indivisible items. Fractional knapsack may take part of the second item and behaves differently. It also does not refute a modified algorithm that compares its greedy result with the best individually feasible item: that comparison selects