Advanced Algorithm Fall 2014

In this lecture, we give more examples of primal-dual approach to design and analyze online algo-rithms. First, we give a roughly ee−1-competitive randomized algorithm for ski-rental problem in Section 1. Then we show an O(logm · log n)-competitive randomized algorithm for online set cover problem in Section 2. In the end, we talk a little bit about approximation problems, and start to analyze the greedy algorithm for offline set cover problem in Section 3. 1 Ski-rental Problem Recap the ski-rental problem: we want to ski for indefinite days, and for each day we need to choose whether to rent ski or to buy ski. We know • cost of renting: $1 • cost of buying: $B Our goal is to minimize total cost. Last time we saw that deterministically we could get a 2-competitive online algorithm. In this section, we show a randomized algorithm with competitive ratio 1 + 1 (1+1/B)B−1, which is roughly e e−1 because as B gets large, (1 + 1/B) B ≈ e, and the ratio goes down to ee−1. Note that the worst case is 2 when B = 1, but B should be more than 1 because otherwise we will not rent skis at all. This bound is originally given by Karlin et al. [KMMO94]. But we will not show the algorithm as they did, instead we adopt a primal-dual approach to get this bound. (See Chapter 3 in [BN09], which gives this algorithm as an example.) In the online version of primal LP, we see one constraint at a time. We have to make online decision to change the variables in order to satisfy the constraint. And through the time the variables should increase monotonously. zi indicates whether to rent on the i-th day, and x indicates whether we buy ski. There are k days in total. For any day i, we have to either rent or buy ski. Primal LP (a.k.a. covering LP): minBx+ k∑ i=1 zi s.t.∀i ∈ [k], x+ zi ≥ 1 x ≥ 0,∀i, zi ≥