Value-Density Greedy Knapsack Has No Constant Approximation Guarantee

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 $0<\epsilon <1$, there is a two-item instance with positive integer sizes and values on which the returned value is at most $\epsilon \mathrm{OPT}$.
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 $0<\epsilon <1$ and set $N=\lceil 1/\epsilon \rceil +1$. Give the knapsack capacity $N$ and the following two items:

Item	Size	Value	Density
$a_1$	$1$	$1$	$1$
$a_2$	$N$	$N-1$	$1-1/N$

All sizes and values are positive integers, and the densities are strictly ordered, so tie-breaking is irrelevant.

Follow the greedy selection

Greedy selects $a_1$ first because $1>1-1/N$. Only $N-1$ capacity remains, so $a_2$ no longer fits. The returned value is $1$.

Both items cannot fit together because $1+N>N$. The second item alone fits and has value $N-1>1$, so the optimum is $N-1$.

Make the ratio as small as requested

Since $N-1=\lceil 1/\epsilon \rceil \ge 1/\epsilon$,
$\frac{\mathrm{GREEDY}}{\mathrm{OPT}}=\frac{1}{N-1}\le \epsilon .$
This construction works for every positive $\epsilon <1$, 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 $a_2$ on this instance.