neal young / Chrobak08Online

Algorithmica 50(4):455478(2008); Latin American Theoretical Informatics (LATIN'06; LNCS 3887:311322)Following Mettu and Plaxton, we study incremental algorithms for the \(k\)medians problem. Such an algorithm must produce a nested sequence \(F_1 \subseteq F_2 \subseteq \cdots \subseteq F_n\) of sets of facilities. Mettu and Plaxton show that incremental metric medians has a (roughly) \(40\)competitive deterministic polynomialtime algorithm. We give improved algorithms, including a \((24+\epsilon)\)competitive deterministic polynomialtime algorithm and a \(5.44\)competitive, randomized, nonpolynomialtime algorithm.
We also consider the competitive ratio with respect to size. An algorithm is \(s\)sizecompetitive if, for each \(k\), the cost of \(F_k\) is at most the minimum cost of any set of \(k\) facilities, while the size of \(F_k\) is at most \(s k\). We present optimally competitive algorithms for this problem.
Our proofs reduce incremental medians to the following online bidding problem: faced with some unknown threshold \(T>0\), an algorithm must submit ``bids'' \(b>0\) until it submits a bid as large as \(T\). The algorithm pays the sum of its bids. We describe optimally competitive algorithms for online bidding.
Our results on costcompetitive incremental medians extend to approximately metric distance functions, incremental fractional medians, and incremental bicriteria approximation.Journal version of [2006].
© Copyrights are reserved by the publishers.
Download for personal and limited academic use only.