Online medians via online bribery
Marek Chrobák, Claire Kenyon, John Noga, Neal E. Young · 2006
Following Mettu and Plaxton [15, 16], we study online algorithms for the k-medians problem. Such an algorithm must produce an incremental sequence F1 ⊆ F2 ⊆ · · · ⊆ Fn ⊆ F of sets of facilities. Mettu and Plaxton show that online metric medians has a (roughly) 40-competitive deterministic polynomial-time algorithm. We give improved algorithms, including a (24 + ǫ)competitive deterministic polynomial-time algorithm and a 2e ≈ 5.44-competitive, randomized, non-polynomial-time algorithm. We also consider the competitive ratio with respect to size. An algorithm is s-size-competitive if, for each k, the cost of Fk is at most the minimum cost of any set of k facilities, while the size of Fk is at most sk. We present optimally competitive algorithms for this problem. Our proofs reduce online medians to the following online bribery problem: faced with some unknown threshold T ∈ R +, an algorithm must submit “bids ” b ∈ R + until it submits a bid as large as T. The algorithm pays the sum of its bids. We describe optimally competitive algorithms for online bribery. Our results on cost-competitive online medians extend to approximately metric distance functions, online fractional medians, and online bicriteria approximation.