Document Open Access Logo

The p-Center Problem in Tree Networks Revisited

Authors Aritra Banik, Binay Bhattacharya, Sandip Das, Tsunehiko Kameda, Zhao Song

PDF
Thumbnail PDF

File

LIPIcs.SWAT.2016.6.pdf
  • Filesize: 0.61 MB
  • 15 pages

Document Identifiers

Author Details

Aritra Banik
Binay Bhattacharya
Sandip Das
Tsunehiko Kameda
Zhao Song

Cite As Get BibTex

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 (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 6:1-6:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.SWAT.2016.6

Abstract

We present two improved algorithms for weighted discrete p-center problem for tree networks with n vertices. One of our proposed algorithms runs in O(n*log(n) + p*log^2(n) * log(n/p)) time. For all values of p, our algorithm thus runs as fast as or faster than the most efficient O(n*log^2(n)) time algorithm obtained by applying Cole's [1987] speed-up technique  to the algorithm due to Megiddo and Tamir [1983], which has remained unchallenged for nearly 30 years.
Our other algorithm, which is more practical, runs in O(n*log(n) + p^2*log^2(n/p)) time, and when p=O(sqrt(n)) it is faster than Megiddo and Tamir's O(n*log^2(n) * log(log(n))) time algorithm [1983].

Subject Classification

Keywords
  • Facility location
  • p-center
  • parametric search
  • tree network
  • sorting network

Metrics

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

References

  1. M. Ajtai, J. Komlós, and E. Szemerédi. An O(n log n) sorting network. In Proc. 15th ACM Symp. on Theory of Comput. (STOC), pages 1-9, 1983. Google Scholar
  2. I. Averbakh and O. Berman. Minimax regret p-center location on a network with demand uncertainty. Location Science, 5:247-254, 1997. Google Scholar
  3. Boaz Ben-Moshe, Binay Bhattacharya, and Qiaosheng Shi. An optimal algorithm for the continuous/discrete weighted 2-center problem in trees. In Proc. LATIN 2006, volume LNCS 3887, pages 166-177, 2006. Google Scholar
  4. R. Benkoczi. Cardinality constrained facility location problems in trees. PhD thesis, School of Computing Science, Simon Fraser University, Canada, 2004. Google Scholar
  5. R. Benkoczi, B. Bhattacharya, M. Chrobak, L. Larmore, and W. Rytter. Faster algorithms for k-median problems in trees. Mathematical Foundations of Computer Science, Springer-Verlag, LNCS 2747:218-227, 2003. Google Scholar
  6. Binay Bhattacharya, Tsunehiko Kameda, and Zhao Song. Minmax regret 1-center on a path/cycle/tree. In Proc. 6th Int'l Conf. on Advanced Engineering Computing and Applications in Sciences (ADVCOMP), pages 108-113, 2012. Google Scholar
  7. Binay Bhattacharya and Qiaosheng Shi. Improved algorithms to network p-center location problems. Computational Geometry, 47:307-315, 2014. Google Scholar
  8. Timothy M. Chan. Klee’s measure problem made easy. In Proc. Symp. on Foundation of Computer Science (FOCS), pages 410-419, 2013. Google Scholar
  9. Bernard Chazelle and Leonidas J. Guibas. Fractional cascading: I. A data structuring technique. Algorithmica, 1:133-162, 1986. Google Scholar
  10. R. Cole. Slowing down sorting networks to obtain faster sorting algorithms. J. ACM, 34:200-208, 1987. Google Scholar
  11. G.N. Frederickson. Optimal algorithms for partitioning trees and locating p centers in trees. Technical Report CSD-TR-1029, Purdue University, 1990. Google Scholar
  12. G.N. Frederickson. Parametric search and locating supply centers in trees. In Proc. Workshop on Algorithms and Data Structures (WADS), Springer-Verlag, volume LNCS 519, pages 299-319, 1991. Google Scholar
  13. Michael T. Goodrich. Zig-zag sort: A simple deterministic data-oblivious sorting algorithm running in O(nlog n) time. arXiv:1403,2777v1 [cs.DS] 11 Mar2014, 2014. Google Scholar
  14. S.L. Hakimi. Optimum locations of switching centers and the absolute centers and medians of a graph. Operations Research, 12:450-459, 1964. Google Scholar
  15. Trevor S. Hale and Christopher R. Moberg. Location science research: A review. Annals of Operations Research, 123:21-35, 2003. Google Scholar
  16. M. Jeger and O. Kariv. Algorithms for finding p-centers on a weighted tree (for relatively small p). Networks, 15:381-389, 1985. Google Scholar
  17. O. Kariv and S.L. Hakimi. An algorithmic approach to network location problems, part 1: The p-centers. SIAM J. Appl. Math., 37:513-538, 1979. Google Scholar
  18. N. Megiddo. Combinatorial optimization with rational objective functions. Math. Oper. Res., 4:414-424, 1979. Google Scholar
  19. N. Megiddo. Applying parallel computation algorithms in the design of serial algorithms. J. ACM, 30:852-865, 1983. Google Scholar
  20. N. Megiddo and A. Tamir. New results on the complexity of p-center problems. SIAM J. Comput., 12:751-758, 1983. Google Scholar
  21. N. Megiddo, A. Tamir, E. Zemel, and R. Chandrasekaran. An O(nlog² n) algorithm for the kth longest path in a tree with applications to location problems. SIAM J. Comput., 10:328-337, 1981. Google Scholar
  22. M.S. Paterson. Improved sorting networks with O(log n) depth. Algorithmica, 5:75-92, 1990. Google Scholar
  23. Joel Seiferas. Sorting networks of logarithmic depth, further simplified. Algorithmica, 53:374-384, 2009. Google Scholar
  24. Q. Shi. Efficient algorithms for network center/covering location optimization problems. PhD thesis, School of Computing Science, Simon Fraser University, Canada, 2008. Google Scholar
  25. A. Tamir. Improved complexity bounds for center location problems on networks by using dynamic structures. SIAM J. Discrete Mathematics, 1:377-396, 1988. 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