HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Knapsack Greedy Approximation: Worst Case

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
caseapproximationknapsackworstgreedy

Problem

I am currently studying approximation algorithms and I have run into an issue with a study problem.

The approximation algorithm is for the general Knapsack problem, and it proposes a greedy approach, where it sorts by the value/weight ratio, and picks the first item in this list that pushes the weight over the limit, and then picks either all the previous items or this particular item, whichever has a greater value.

The claim is that there is at least one case where this algorithm provides a value half that of the optimal value, but after many fruitless attempts I don't see a way to do this.

I have tried many value/weight pairs of 1/1 with a last pair of 5/6, resulting in a ratio of 5/9. Close, but even if I continue this process I am only going to approach a ratio of 1/2, but never achieve it.

Any hints as to how to proceed?

Solution

The approximation ratio is always strictly larger than $1/2$. Let $p_1,\ldots,p_{k-1}$ be the values of the items picked by algorithm, and let $p_k$ be the value of the next item which would have been picked had it fit. Let $\alpha$ be the fraction of $p_k$ that does fit – so $\alpha OPT. $$
The algorithm picks either items $1,\ldots,k-1$ or only item $k$, and there is some choice that results in strictly more than $OPT/2$.

Context

StackExchange Computer Science Q#41381, answer score: 7

Revisions (0)

No revisions yet.