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).

Problem 15 Solution: "For Science"

Specify a bijective mapping that associates each possible ordering with an integer in the range [1,24]. It does not matter how you do this; one way is in lexicographic order (say the wormholes are marked A, B, C, D, then you would have 1 = ABCD, 2 = ABDC, 3 = ACBD, 4 = ACDB, etc). Then you can use binary search to find the correct number by asking questions of the form "Is the number corresponding to the correct ordering less than or equal to X?"

Since there are 24 possibilities, this takes ceil(log_2(24)) = 5 questions.

The generalization is obvious - if there are N wormholes then you map each possible ordering to an integer int he range [1,N!], and so the algorithm takes ceil(log_2(N!)) = O(n log n) questions.

The proof of optimality is easy: If there are k questions, then the number of possible ways of answering those questions is at most 2^k, so if 2^k < N! (which happens if k < log_2(N!)) there is no possible way of distinguishing between the N! possibilities using just the k questions.

[The trick to this question is that you get to ask *any* yes-or-no question; you are not limited to questions of the form "Does X come before Y" that most sorting algorithms use. As an aside, the proof of optimality above is also the standard argument use to show that no comparison-based sorting algorithm can run in better than O(n log n) time.]