Exercises
- A core problem for an online machine scheduling algorithm is whether to make a level or a skewed schedule. For instance, just considering \( m=2 \) and the sequences \( 1 \), \( 1 \) and \( 1 \), \( 1 \), \( 2 \), we do not know what the best option is for the second job: placing it on the same machine as the first job or not. (Because this depends on the future: do we receive a third job of size \( 2 \) or not?) Try to randomize the decision as we did for the Treasure Hunt problem in the lecture. Assuming you get one of these two sequences, can you get an expected ratio smaller than \( \frac32 \)?
- A Professor Larsen with extremely poor eyesight is at a long, long wall. He's told that there is a hole somewhere where he can get out, but he won't be able to see it unless he's right at it; and he doesn't know if it's to the left or to the right. The hole is a whole number of steps away from the professor. Devise an algorithm the professor can use to escape. What's the competitive ratio of your algorithm? (Of course, Opt is just the distance from the professor to the hole.)
- Show an example where lazy Dc benefits from being lazy and one where it doesn't.
- Show that if there exists an infinite family of sequences such that 1) for some fixed constant \( b > 0 \), we have that Alg\( (σ) ≥ k \)·Opt\( (σ) - b \) for any \( σ \) in the family, and 2) for any \( d \), there exists a \( σ \) in the family such that Opt\( (σ) ≥ d \), then Alg cannot be \( (k - \epsilon) \)-competitive for any \( \epsilon > 0 \).
- Prove that there exists a minimum weight matching where the server Dc moves (when it only moves one) is matched to the server Opt just moved.
- For the Treasure Hunt problem, show that \( 3/2 \) is the worst ratio.
- Discuss whether or not one should assume that the adversary knows the coin flips of the algorithm - in the light that we want results in our model to say something about the real world.
- Consider how one might generalize Dc to working on trees. No proofs are expected.