Oblivious Medians Via Online Bidding (Extended Abstract)
Marek Chrobák, Claire Kenyon, John Noga, Neal E. Young · 2006
Abstract. Following Mettu and Plaxton [22, 21], we study oblivious algorithms for the k-medians problem. Such an algorithm produces an incremental sequence of facility sets. We give improved algorithms, including a (24 + ɛ)-competitive deterministic polynomial algorithm and a2e ≈ 5.44-competitive randomized non-polynomial algorithm. Our approach is similar to that of [18], which was done independently. We then consider the competitive ratio with respect to size. Analgorithm is s-size-competitive if, for each k, thecostofFk 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 oblivious medians to the following online bidding problem: faced with some unknown threshold T ∈ R +, an algorithm must submit “bids ” b ∈ R + until it submits a bid b ≥ T,payingthesumofits bids. We describe optimally competitive algorithms for online bidding. Some of these results extend to approximately metric distance functions,obliviousfractionalmedians,andobliviousbicriteriaapproximation.