An approximation algorithm for the hierarchical median problem
Tóm tắt
The hierarchical median problem asks for a hierarchical sequence of solutions to the k-median problems of growing cardinality. The best algorithm known for this problem in the general metric case has competitive ratio 20.71. In the paper, the case is under study that the clients and facilities lie on the real line, as well as the case of a Euclidean space. An algorithm is proposed with competitive ratio 8 in the case of the real line, and 8 + 4√2 (approximately 13.66), in the Euclidean case.
Tài liệu tham khảo
V. V. Shenmaier, “An Approximate Solution Algorithm for the One-Dimensional Online Median Problem,” Diskret. Anal. Issled. Oper., Ser. 1, 14(2), 95–101 (2007) [J. Appl. Industr. Math. 2 (3), 421–425 (2008)].
M. Chrobak, C. Kenyon, J. Noga, and N. Young, “Online Medians Via Online Bribery,” in Lecture Notes on Computer Science, Vol. 3887: Proceedings of the 7th Latin American Theoretical Informatics Symposium (Springer, Berlin, 2006), pp. 311–322.
S. Dasgupta, “Performance Guarantees for Hierarchical Clustering,” in Proceedings of the 15th Conference on Computational Learning Theory (Springer, London, 2002), pp. 351–363.
G. Lin, C. Nagarajan, R. Rajaraman, and D. P. Williamson, “A General Approach for Incremental Approximation and Hierarchical Clustering,” in Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms (ACM Press, New York, 2006), pp. 1147–1156.
Discrete Location Theory, Ed. by P. Mirchandani and R. Francis (Wiley, New York, 1990).
C. G. Plaxton, “Approximation Algorithms for Hierarchical Location Problems,” in Proceedings of the 35th ACM Symposium on Theory of Computing (ACM Press, New York, 2003), pp. 40–49.