The ModGreedyKnapsack Algorithm is a PTAS

Let be the max-value knapsack problem with

• a fixed ,
• a finite set of items ,
• a size function ,
• a value function , and
• a knapsack capacity of .

Consider the following algorithm :

1. Enumerate all of at most size , i.e., enumerate all combinations.
2. Discard the branch if . Otherwise, scan the items in in descending order of the ratio and add an item whenever it fits, i.e., whenever . The set of those greedily-selected items is denoted by .
3. Each branch constructs a (possibly non-optimal) solution .
4. At the end, choose an of highest value.

To prove that the described algorithm is a PTAS, we have to show the following two properties:

1. .
2. , with being the running time.

Approximation guarantee

Let be an optimal solution for . Consider both cases:

1. : The branch is enumerated. Its candidate has value at least , so the algorithm outputs an optimal solution.
2. : The optimal solution isn’t fully covered by the all-enumeration, which requires special treatment.

Consider the branch in which consists of the most valuable items of . This branch fills the remaining capacity greedily with items

where .

How does relate to ? If greedy selects every item in , then is optimal. Otherwise, let be the first item of that does not fit. Immediately before is considered, define

• Optimal items: Items from that were selected before .
• Missed items: Items from that were not selected before . In particular, .
• Non-optimal items: Items outside that were selected before .

The first missed optimal item marks a cut in the density-ordered scan:

Let be the partial candidate immediately before is considered. Since the final candidate contains ,

Consider the missing items first. Since is the first missed optimal item and the items are processed in descending order of ratio, we have

Equivalently:

Therefore, we found an upper bound for the first term already:

Next, we want to find a lower bound for . Every was selected before , so ‘s ratio must be greater than or equal to ‘s ratio, i.e.,

Equivalently,

Therefore:

Equivalently:

Putting them together yields

What’s ? We know that the optimal solution consists of the enumerated items, the optimal items selected before , and the missing optimal items, i.e.,

Hence, we can infer from the feasibility of that

Equivalently:

The right-hand side is precisely the free capacity immediately before is considered. Since does not fit, we know that

The two knapsacks below compare the same shared prefix . The current greedy prefix spends some capacity on ; the optimal solution instead spends capacity on .

Therefore,

It remains to relate to . Since contains the most valuable items of and , every item in has value at least . Hence,

Equivalently,

The reason for the denominator is that contains guessed items, each worth at least , together with itself:

Putting both bounds together yields

By the choice , we have

Consequently,

Since the algorithm returns the most valuable candidate among all enumerated branches, its output has at least the value of this particular . Therefore,

which proves the approximation condition.

Running-time

The density order can be computed once and reused by every branch. Sorting the items by takes time. Ratios need not be represented explicitly: two items and can be compared by cross-multiplying

The number of enumerated subsets is

For each subset , the algorithm computes and then scans the density-ordered list once, skipping the items in and adding every item that fits. Since is fixed for a fixed , this requires time per branch.

Consequently,

For every fixed , the value

is constant with respect to the input. Moreover,

so the running time simplifies to

Since , this is polynomial in for every fixed . Under the unit-cost model, we may choose

and obtain

Arithmetic on binary-encoded sizes and values contributes only another factor in the bit model, where is a constant independent of and . In that model, choose instead

Thus, for every fixed , the algorithm runs in polynomial time. Together with the approximation guarantee, this proves that is a PTAS.