Chrobak, Marek; Hurand, Mathilde 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]. Cited in 2 Documents MSC: 90B80 Discrete location and assignment 68W25 Approximation algorithms 68W40 Analysis of algorithms Keywords:incremental medians; approximation algorithm; online algorithm; analysis of algorithms Citations:Zbl 1128.90550 PDFBibTeX XMLCite \textit{M. Chrobak} and \textit{M. Hurand}, Lect. Notes Comput. Sci. 4927, 207--217 (2008; Zbl 1130.90026) 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.