Oblivious Medians via Online Bidding

Following Mettu and Plaxton, we study online algorithms for the
k-medians problem. Such an algorithm must produce a nested sequence 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+epsilon)-competitive deterministic polynomial-time algorithm and a
5.44- competitive, randomized, non-polynomial-time algorithm. We also
consider the competitive ratio with respect to size, where we compare
the optimal solution with k facilities to a solution with more
facilities. We present optimally competitive algorithms for this
problem. Our proofs reduce online medians to a very simple "online
bidding" problem. Many analysis of online problems can be rephrased as
reductions to online bidding. This is joint work with Marek Chrobak,
John Noga and Neal Young.