Document Open Access Logo

An O(n^2 log^2 n) Time Algorithm for Minmax Regret Minsum Sink on Path Networks

Authors Binay Bhattacharya, Yuya Higashikawa, Tsunehiko Kameda, Naoki Katoh

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2018.14.pdf
  • Filesize: 0.54 MB
  • 13 pages

Document Identifiers

Author Details

Binay Bhattacharya
  • School of Computing Science, Simon Fraser University, Burnaby, Canada
Yuya Higashikawa
  • School of Business Administration, University of Hyogo, Kobe, Japan
Tsunehiko Kameda
  • School of Computing Science, Simon Fraser University, Burnaby, Canada
Naoki Katoh
  • School of Science and Technology, Kwansei Gakuin University, Sanda, Japan

Cite As Get BibTex

Binay Bhattacharya, Yuya Higashikawa, Tsunehiko Kameda, and Naoki Katoh. An O(n^2 log^2 n) Time Algorithm for Minmax Regret Minsum Sink on Path Networks. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 14:1-14:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ISAAC.2018.14

Abstract

We model evacuation in emergency situations by dynamic flow in a network. We want to minimize the aggregate evacuation time to an evacuation center (called a sink) on a path network with uniform edge capacities. The evacuees are initially located at the vertices, but their precise numbers are unknown, and are given by upper and lower bounds. Under this assumption, we compute a sink location that minimizes the maximum "regret." We present the first sub-cubic time algorithm in n to solve this problem, where n is the number of vertices. Although we cast our problem as evacuation, our result is accurate if the "evacuees" are fluid-like continuous material, but is a good approximation for discrete evacuees.

Subject Classification

ACM Subject Classification
  • Networks → Network algorithms
  • Mathematics of computing → Graph algorithms
  • Applied computing → Transportation
Keywords
  • Facility location
  • minsum sink
  • evacuation problem
  • minmax regret
  • dynamic flow path network

Metrics

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

Related Versions

References

  1. Guru Prakash Arumugam, John Augustine, Mordecai Golin, and Prashanth Srikanthan. A Polynomial Time Algorithm for Minimax-Regret Evacuation on a Dynamic Path. arXiv:1404,5448 v1 [cs.DS] 22 April, 2014. Google Scholar
  2. R. Benkoczi, B. Bhattacharya, Y. Higashikawa, T. Kameda, and N. Katoh. Minsum k-sink on dynamic flow path network. In Combinatorial Algorithms (Iliopoulos, Costas, Leong, Hon Wai, Sung, Wing-Kin, Eds.), Springer-Verlag LNCS 110979, pages 78-89, 2018. Google Scholar
  3. Binay Bhattacharya, Yuya Higashikawa, Tiko Kameda, and Naoki Katoh. Minmax regret 1-sink for aggregate evacuation time on path networks. arXiv:1806.00814 Oct 2018. Google Scholar
  4. Binay Bhattacharya and Tsunehiko Kameda. Improved algorithms for computing minmax regret sinks on path and tree networks. Theoretical Computer Science, 607:411-425, November 2015. Google Scholar
  5. Siu-Wing Cheng, Yuya Higashikawa, Naoki Katoh, Guanqun Ni, Bing Su, and Yinfeng Xu. Minimax regret 1-sink location problem in dynamic path networks. In Proc. Annual Conf. on Theory and Applications of Models of Computation (T-H.H. Chan, L.C. Lau, and L. Trevisan, Eds.), Springer-Verlag, LNCS 7876, pages 121-132, 2013. Google Scholar
  6. L.R. Ford and D.R. A. Fulkerson. Constructing maximal dynamic flows from static flows. Operations Research, 6(3):419-433, 1958. Google Scholar
  7. Mordecai Golin and Sai Sandeep. Minmax-regret k-sink location on a dynamic tree network with uniform capacities. arXiv:1806.03814v1 [cs.DS] 11 June, 2018. Google Scholar
  8. H.W. Hamacher and S.A. Tjandra. Mathematical modelling of evacuation problems: a state of the art. in: Pedestrian and Evacuation Dynamics, Springer Verlag,, pages 227-266, 2002. Google Scholar
  9. J. Hershberger. Finding the upper envelope of n line segments in O(nlog n) time. Information Processing Letters, 33(4):169-174, 1989. Google Scholar
  10. Yuya Higashikawa, John Augustine, Siu-Wing Cheng, Mordecai J. Golin, Naoki Katoh, Guanqun Ni, Bing Su, and Yinfeng Xu. Minimax regret 1-sink location problem in dynamic path networks. Theoretical Computer Science, 588(11):24-36, 2015. Google Scholar
  11. Yuya Higashikawa, Siu-Wing Cheng, Tsunehiko Kameda, Naoki Katoh, and Shun Saburi. Minimax regret 1-median problem in dynamic path networks. Theory of Computing Systems, 62(6):1392-1408, August 2018. Google Scholar
  12. Yuya Higashikawa, Mordecai J. Golin, and Naoki Katoh. Minimax regret sink location problem in dynamic tree networks with uniform capacity. Journal of Graph Algorithms and Applications, 18(4):539-555, 2014. Google Scholar
  13. Yuya Higashikawa, Mordecai J. Golin, and Naoki Katoh. Multiple sink location problems in dynamic path networks. Theoretical Computer Science, 607(1):2-15, 2015. Google Scholar
  14. Oded Kariv and S.Louis Hakimi. An algorithmic approach to network location problems, Part II: The p-median. SIAM J. Appl. Math., 37:539-560, 1979. Google Scholar
  15. P. Kouvelis and G. Yu. Robust Discrete Optimization and its Applications. Kluwer Academic Publishers, London, 1997. Google Scholar
  16. Satoko Mamada, Takeaki Uno, Kazuhisa Makino, and Satoru Fujishige. An O(nlog² n) algorithm for a sink location problem in dynamic tree networks. Discrete Applied Mathematics, 154:2387-2401, 2006. Google Scholar
  17. Haitao Wang. Minmax Regret 1-Facility Location on Uncertain Path Networks. European J. of Operational Research, 239(3):636-643, 2014. 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