Document Open Access Logo

An O(n log n)-Time Algorithm for the k-Center Problem in Trees

Authors Haitao Wang, Jingru Zhang

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2018.72.pdf
  • Filesize: 488 kB
  • 15 pages

Document Identifiers

Author Details

Haitao Wang
Jingru Zhang

Cite As Get BibTex

Haitao Wang and Jingru Zhang. An O(n log n)-Time Algorithm for the k-Center Problem in Trees. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 72:1-72:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.SoCG.2018.72

Abstract

We consider a classical k-center problem in trees. Let T be a tree of n vertices and every vertex has a nonnegative weight. The problem is to find k centers on the edges of T such that the maximum weighted distance from all vertices to their closest centers is minimized. Megiddo and Tamir (SIAM J. Comput., 1983) gave an algorithm that can solve the problem in O(n log^2 n) time by using Cole's parametric search. Since then it has been open for over three decades whether the problem can be solved in O(n log n) time. In this paper, we present an O(n log n) time algorithm for the problem and thus settle the open problem affirmatively.

Subject Classification

Keywords
  • k-center
  • trees
  • facility locations

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. P.K. Agarwal and J.M. Phillips. An efficient algorithm for 2D Euclidean 2-center with outliers. In Proceedings of the 16th Annual European Conference on Algorithms(ESA), pages 64-75, 2008. Google Scholar
  2. M. Ajtai, J. Komlós, and E. Szemerédi. An O(nlog n) sorting network. In Proc. of the 15th Annual ACM Symposium on Theory of Computing (STOC), pages 1-9, 1983. Google Scholar
  3. A. Banik, B. Bhattacharya, S. Das, T. Kameda, and Z. Song. The p-center problem in tree networks revisited. In Proc. of the 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), pages 6:1-6:15, 2016. Google Scholar
  4. B. Bhattacharya and Q. Shi. Optimal algorithms for the weighted p-center problems on the real line for small p. In Proc. of the 10th International Workshop on Algorithms and Data Structures, pages 529-540, 2007. Google Scholar
  5. P. Brass, C. Knauer, H.-S. Na, C.-S. Shin, and A. Vigneron. The aligned k-center problem. International Journal of Computational Geometry and Applications, 21:157-178, 2011. Google Scholar
  6. H Brönnimann and B. Chazelle. Optimal slope selection via cuttings. Computational Geometry: Theory and Applications, 10(1):23-29, 1998. Google Scholar
  7. T.M. Chan. More planar two-center algorithms. Computational Geometry: Theory and Applications, 13:189-198, 1999. Google Scholar
  8. R. Chandrasekaran and A. Tamir. Polynomially bounded algorithms for locating p-centers on a tree. Mathematical Programming, 22(1):304-315, 1982. Google Scholar
  9. D.Z. Chen, J. Li, and H. Wang. Efficient algorithms for the one-dimensional k-center problem. Theoretical Computer Science, 592:135-142, 2015. Google Scholar
  10. D.Z. Chen and H. Wang. Approximating points by a piecewise linear function. Algorithmica, 88:682-713, 2013. Google Scholar
  11. D.Z. Chen and H. Wang. A note on searching line arrangements and applications. Information Processing Letters, 113:518-521, 2013. Google Scholar
  12. R. Cole. Slowing down sorting networks to obtain faster sorting algorithms. Journal of the ACM, 34(1):200-208, 1987. Google Scholar
  13. G. Cormode and A. McGregor. Approximation algorithms for clustering uncertain data. In Proc. of the 27t Symposium on Principles of Database Systems (PODS), pages 191-200, 2008. Google Scholar
  14. G. Frederickson and D. Johnson. Generalized selection and ranking: Sorted matrices. SIAM Journal on Computing, 13(1):14-30, 1984. Google Scholar
  15. G.N. Frederickson. Optimal algorithms for tree partitioning. In Proc. of the 2nd Annual ACM-SIAM Symposium of Discrete Algorithms (SODA), pages 168-177, 1991. Google Scholar
  16. G.N. Frederickson. Parametric search and locating supply centers in trees. In Proc. of the 2nd International Workshop on Algorithms and Data Structures (WADS), pages 299-319, 1991. Google Scholar
  17. G.N. Frederickson and D.B. Johnson. Finding kth paths and p-centers by generating and searching good data structures. Journal of Algorithms, 4(1):61-80, 1983. Google Scholar
  18. L. Huang and J. Li. Stochastic k-center and j-flat-center problems. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 110-129, 2017. Google Scholar
  19. M. Jeger and O. Kariv. Algorithms for finding P-centers on a weighted tree (for relatively small P). Networks, 15(3):381-389, 1985. Google Scholar
  20. O. Kariv and S.L. Hakimi. An algorithmic approach to network location problems. I: The p-centers. SIAM Journal on Applied Mathematics, 37(3):513-538, 1979. Google Scholar
  21. A. Karmakar, S. Das, S.C. Nandy, and B.K. Bhattacharya. Some variations on constrained minimum enclosing circle problem. Journal of Combinatorial Optimization, 25(2):176-190, 2013. Google Scholar
  22. M. Katz and M. Sharir. Optimal slope selection via expanders. Information Processing Letters, 47(3):115-122, 1993. Google Scholar
  23. N. Megiddo. Linear-time algorithms for linear programming in R³ and related problems. SIAM Journal on Computing, 12(4):759-776, 1983. Google Scholar
  24. N. Megiddo and K.J. Supowit. On the complexity of some common geometric location problems. SIAM Journal on Comuting, 13:182-196, 1984. Google Scholar
  25. N. Megiddo and A. Tamir. New results on the complexity of p-centre problems. SIAM Journal on Computing, 12(4):751-758, 1983. Google Scholar
  26. N. Megiddo, A. Tamir, E. Zemel, and R. Chandrasekaran. An O(n log² n) algorithm for the k-th longest path in a tree with applications to location problems. SIAM Journal on Computing, 10:328-337, 1981. Google Scholar
  27. H. Wang and J. Zhang. One-dimensional k-center on uncertain data. Theoretical Computer Science, 602:114-124, 2015. Google Scholar
  28. H. Wang and J. Zhang. Line-constrained k-median, k-means, and k-center problems in the plane. International Journal of Computational Geometry and Applications, 26:185-210, 2016. Google Scholar
  29. H. Wang and J. Zhang. A note on computing the center of uncertain data on the real line. Operations Research Letters, 44:370-373, 2016. Google Scholar
  30. H. Wang and J. Zhang. Computing the center of uncertain points on tree networks. Algorithmica, 609:32-48, 2017. Google Scholar
  31. H. Wang and J. Zhang. Covering uncertain points in a tree. In Proc. of the 15th Algorithms and Data Structures Symposium (WADS), pages 557-568, 2017. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact