Problem 16 Solution: "Fall Out Pick Up"

(Note: We will identify an object of weight a and value b by the notation [a,b].)

(a) and (b).

No. Suppose there was an algorithm with competitive ratio K > 0. Then the adversary operates as follows:

- Choose an integer T that is high enough so that 1/T < K.
- Give the algorithm a capacity (T^2).
- At first, provide the item [T^2, T]. If the algorithm doesn't take the item, then stop there; the algorithm got 0 while it could have gotten T, contradicting the fact that it has competitive ratio K. If it does, then keep providing [1,1] items. If the algorithm ever drops the [T^2, T] item to pick up a [1,1], then stop there; the algorithm got 1 when it could have gotten T. Otherwise, stop after you have provided T^2 [1,1] items; by this point the algorithm got T when it could have gotten T^2. So the algorithm has only achieved 1/T of the optimal, contradicting the competitive ratio K.

So by contradiction, there is no algorithm with competitive ratio K > 0.

(c) Each time you see a new item, pick up the item, then drop the items with the lowest value-to-weight ratio until you get within capacity (this may include dropping the new item; in this case you essentially don't pick it up). If this never involves dropping any items, then you will have picked up every item you got so of course it is optimal. If this does involve dropping items, then at the end you will have at least C-M out of your capacity C filled (because each time you drop an item it reduces the total by at most M, and you don't drop until you're over C). Also, since you're storing the items with the highest cost-to-weight ratio, the space that you did fill you are getting as much value out of it as you can. So the competitive ratio is at least (C-M)/C = 1-(M/C).