Abstract
The hierarchical median problem consists of finding a hierarchical assignment function sequence of solutions to the well-known k-median problems with growing cardinality. This sequence is said to be r-competitive if the cost of each solution is at most r times of the optimum cost of median problem with a same cardinality, where r is called the competitive ratio. Previously the best algorithm available for this problem has competitive ratio 20.71. In this paper an improved algorithm is proposed with competitive ratio factor 16.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Daskin M S. Network and Discrete Location: Models, Algorithms, and Applications. New York: Wiley, 1995
Drezner Z, Hamacher H. Facility Location: Applications and Theory. Berlin: Springer, 2002
Eiselt H A, Marianov V. Foundations of Location Analysis. Berlin: Springer, 2011
Arya V, Garg N, Khandekar R, et al. Local search heuristics for k-median and facility location problems. SIAM J Comput, 2008, 37: 1472–1498
Mladenović N, Brimberg J, Hansen P, et al. The p-median problem: a survey of metaheuristic approaches. Eur J Oper Res, 2007, 179: 927–939
Shmoys D B. Approximation algorithms for facility location problems. In: Proceedings of the 3rd International Workshop on Approximation Algorithms for Combinatorial Optimization, Saarbrücken, 2000. 27–33
Plaxton C G. Approximation algorithms for hierarchical location problems. J Comput Syst Sci, 2006, 72: 425–443
Barthélemy J P, Brucker F, Osswald C. Combinatorial optimization and hierarchical classifications. Ann Oper Res, 2007, 153: 179–214
Lin G L, Nagarajan C, Rajamaran R, et al. A general approach for incremental approximation and hierarchical clustering. SIAM J Comput, 2010, 3: 3633–3669
Shenmaier V V. An approximation algorithm for the hierarchical median problem. J Appl Ind Math, 2009, 3: 128–132
Mettu R R, Plaxton C G. The online median problem. SIAM J Comput, 2003, 32: 816–832
Chrobak M, Hurand M. Better bounds for incremental medians. Theor Comput Sci, 2011, 412: 594–601
Chrobak M, Kenyon C, Noga J, et al. Incremental medians via online bidding. Algorithmica, 2008, 50: 455–478
Dai W Q, Zeng X J. Incremental facility location problem and its competitive algorithms. J Comb Optim, 2010, 20: 307–320
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Dai, W. A 16-competitive algorithm for hierarchical median problem. Sci. China Inf. Sci. 57, 1–7 (2014). https://doi.org/10.1007/s11432-014-5065-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11432-014-5065-0