LIPIcs.ISAAC.2019.27.pdf
- Filesize: 0.59 MB
- 11 pages
Document
The Weighted k-Center Problem in Trees for Fixed k
Authors
-
Part of:
Volume:
30th International Symposium on Algorithms and Computation (ISAAC 2019)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Algorithms and Computation (ISAAC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2019-11-28
Cite AsGet BibTex
Binay Bhattacharya, Sandip Das, and Subhadeep Ranjan Dev. The Weighted k-Center Problem in Trees for Fixed k. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 27:1-27:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ISAAC.2019.27
https://doi.org/10.4230/LIPIcs.ISAAC.2019.27
Abstract
We present a linear time algorithm for the weighted k-center problem on trees for fixed k. This partially settles the long-standing question about the lower bound on the time complexity of the problem. The current time complexity of the best-known algorithm for the problem with k as part of the input is O(n log n) by Wang et al. [Haitao Wang and Jingru Zhang, 2018]. Whether an O(n) time algorithm exists for arbitrary k is still open.
Subject Classification
ACM Subject Classification
- Theory of computation → Facility location and clustering
- Theory of computation → Network optimization
Keywords
- facility location
- prune and search
- parametric search
- k-center problem
- conditional k-center problem
- trees
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Aritra Banik, Binay Bhattacharya, Sandip Das, Tsunehiko Kameda, and Zhao Song. The p-Center Problem in Tree Networks Revisited. In 15th Scandinavian Symposium and Workshops on Algorithm Theory, 2016.
-
Boaz Ben-Moshe, Binay Bhattacharya, and Qiaosheng Shi. An Optimal Algorithm for the Continuous/Discrete Weighted 2-Center Problem in Trees. In José R. Correa, Alejandro Hevia, and Marcos Kiwi, editors, LATIN 2006: Theoretical Informatics, pages 166-177, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg.
-
Boaz Ben-Moshe, Binay Bhattacharya, Qiaosheng Shi, and Arie Tamir. Efficient algorithms for center problems in cactus networks. Theoretical Computer Science, 378(3):237-252, 2007. Algorithms and Computation.
- Binay Bhattacharya, Sandip Das, and Tsunehiko Kameda. Linear-time fitting of a k-step function. Discrete Applied Mathematics, 2017. URL: https://doi.org/10.1016/j.dam.2017.11.005.
-
Binay Bhattacharya and Qiaosheng Shi. Optimal Algorithms for the Weighted p-Center Problems on the Real Line for Small p. In Frank Dehne, Jörg-Rüdiger Sack, and Norbert Zeh, editors, Algorithms and Data Structures, pages 529-540, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg.
-
Richard Cole. Slowing Down Sorting Networks To Obtain Faster Sorting Algorithm. In Foundations of Computer Science, 1984. 25th Annual Symposium on, pages 255-260. IEEE, 1984.
-
Greg N. Frederickson. Parametric search and locating supply centers in trees. In Frank Dehne, Jörg-Rüdiger Sack, and Nicola Santoro, editors, Algorithms and Data Structures, pages 299-319, Berlin, Heidelberg, 1991. Springer Berlin Heidelberg.
-
M Jeger and Oded Kariv. Algorithms for finding P-centers on a weighted tree (for relatively small P). Networks, 15(3):381-389, 1985.
-
Oded Kariv and S Louis Hakimi. An algorithmic approach to network location problems. I: The p-centers. SIAM Journal on Applied Mathematics, 37(3):513-538, 1979.
-
Arindam Karmakar, Sandip Das, Subhas C Nandy, and Binay K Bhattacharya. Some variations on constrained minimum enclosing circle problem. Journal of Combinatorial Optimization, 25(2):176-190, 2013.
-
Nimrod Megiddo. Linear-time algorithms for linear programming in ℝ³ and related problems. SIAM journal on computing, 12(4):759-776, 1983.
-
Nimrod Megiddo and Arie Tamir. New results on the complexity of p-centre problems. SIAM Journal on Computing, 12(4):751-758, 1983.
-
Edward Minieka. Conditional centers and medians of a graph. Networks, 10(3):265-272, 1980.
-
Qiaosheng Shi. Efficient algorithms for network center/covering location optimization problems. PhD thesis, School of Computing Science-Simon Fraser University, 2008.
-
Haitao Wang and Jingru Zhang. An O(n log n)-Time Algorithm for the k-Center Problem in Trees. In Bettina Speckmann and Csaba D. Tóth, editors, 34th International Symposium on Computational Geometry (SoCG 2018), volume 99 of Leibniz International Proceedings in Informatics (LIPIcs), pages 72:1-72:15, Dagstuhl, Germany, 2018.