×

Better bounds for incremental medians. (English) Zbl 1130.90026

Kaklamanis, Christos (ed.) et al., Approximation and online algorithms. 5th international workshop, WAOA 2007, Eilat, Israel, October 11-12, 2007. Revised papers. Berlin: Springer (ISBN 978-3-540-77917-9/pbk). Lecture Notes in Computer Science 4927, 207-217 (2008).
Summary: In the incremental version of the well-known \(k\)-median problem the objective is to compute an incremental sequence of facility sets \(F _{1} \subseteq F _{2} \subseteq \dots . \subseteq F _{n }\), where each \(F _{k }\) contains at most \(k\) facilities. We say that this incremental medians sequence is \(R\)-competitive if the cost of each \(F _{k }\) is at most \(R\) times the optimum cost of \(k\) facilities. The smallest such \(R\) is called the competitive ratio of the sequence \(2+4\sqrt2\approx7.656\). Mettu and Plaxton presented a polynomial-time algorithm that computes an incremental sequence with competitive ratio \(\approx 30\). They also showed a lower bound of 2. The upper bound on the ratio was improved to 8. We improve both bounds in this paper. We first show that no incremental sequence can have competitive ratio better than 2.01 and we give a probabilistic construction of a sequence whose competitive ratio is at most \(2+4\sqrt{2} \approx 7.656\). We also propose a new approach to the problem that for instances that we refer to as equable achieves an optimal competitive ratio of 2.
For the entire collection see [Zbl 1130.68010].

MSC:

90B80 Discrete location and assignment
68W25 Approximation algorithms
68W40 Analysis of algorithms

Citations:

Zbl 1128.90550
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arya, V.; Garg, N.; Khandekar, R.; Meyerson, A.; Munagala, K.; Pandit, V., Local search heuristic for k-median and facility location problems, STOC. Proc. 33rd Symp. Theory of Computing, 21-29 (2001), New York: ACM, New York · Zbl 1323.90031
[2] Arya, V.; Garg, N.; Khandekar, R.; Meyerson, A.; Munagala, K.; Pandit, V., Local search heuristics for k-median and facility location problems, SIAM Journal on Computing, 33, 3, 544-562 (2004) · Zbl 1105.68118 · doi:10.1137/S0097539702416402
[3] Chrobak, M., Kenyon, C.: Competitiveness via doubling. SIGACT News, 115-126 (2006)
[4] Chrobak, M.; Kenyon, C.; Noga, J.; Young, N.; Correa, J. R.; Hevia, A.; Kiwi, M., Online medians via online bidding, LATIN 2006: Theoretical Informatics, 311-322 (2006), Heidelberg: Springer, Heidelberg · Zbl 1145.68583 · doi:10.1007/11682462_31
[5] Lin, G., Nagarajan, C., Rajamaran, R., Williamson, D.P.: A general approach for incremental approximation and hierarchical clustering. In: SODA. Proc. 17th Symp. on Discrete Algorithms, pp. 1147-1156 (2006) · Zbl 1192.68978
[6] Mettu, R. R.; Plaxton, C. G.; Ramgopal, R., The online median problem, FOCS. Proc. 41st Symp. Foundations of Computer Science, 339-348 (2000), Los Alamitos: IEEE, Los Alamitos · doi:10.1109/SFCS.2000.892122
[7] Mettu, R. R.; Plaxton, C. G., The online median problem, SIAM J. Comput., 32, 816-832 (2003) · Zbl 1128.90550 · doi:10.1137/S0097539701383443
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.