Search Results

Documents authored by Katoh, Naoki

Document
DOI: 10.4230/OASIcs.ATMOS.2021.13
Locating Evacuation Centers Optimally in Path and Cycle Networks

Authors: Robert Benkoczi, Binay Bhattacharya, Yuya Higashikawa, Tsunehiko Kameda, Naoki Katoh, and Junichi Teruyama

Published in: OASIcs, Volume 96, 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)

Abstract
We present dynamic flow algorithms to solve the k-sink problem whose aim is to locate k sinks (evacuation centers) in such a way that the evacuation time of the last evacuee is minimized. In the confluent model, the evacuees originating from or passing through a vertex must evacuate to the same sink, and most known results on the k-sink problem adopt the confluent model. When the edge capacities are uniform (resp. general), our algorithms for non-confluent flow in the path networks run in O(n + k² log² n) (resp. O(n log(n) + k² log⁵ n)) time, where n is the number of vertices. Our algorithms for cycle networks run in O(k²n log² n) (resp. O(k²n log⁵ n)) time, when the edge capacities are uniform (resp. general).
Cite as

Robert Benkoczi, Binay Bhattacharya, Yuya Higashikawa, Tsunehiko Kameda, Naoki Katoh, and Junichi Teruyama. Locating Evacuation Centers Optimally in Path and Cycle Networks. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 13:1-13:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{benkoczi_et_al:OASIcs.ATMOS.2021.13,
  author =	{Benkoczi, Robert and Bhattacharya, Binay and Higashikawa, Yuya and Kameda, Tsunehiko and Katoh, Naoki and Teruyama, Junichi},
  title =	{{Locating Evacuation Centers Optimally in Path and Cycle Networks}},
  booktitle =	{21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
  pages =	{13:1--13:19},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-213-6},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{96},
  editor =	{M\"{u}ller-Hannemann, Matthias and Perea, Federico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.13},
  URN =		{urn:nbn:de:0030-drops-148825},
  doi =		{10.4230/OASIcs.ATMOS.2021.13},
  annote =	{Keywords: Efficient algorithms, facility location, minmax sink, evacuation problem, dynamic flow in network}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.14
An O(n^2 log^2 n) Time Algorithm for Minmax Regret Minsum Sink on Path Networks

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

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

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.
Cite as

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)

Copy BibTex To Clipboard

@InProceedings{bhattacharya_et_al:LIPIcs.ISAAC.2018.14,
  author =	{Bhattacharya, Binay and Higashikawa, Yuya and Kameda, Tsunehiko and Katoh, Naoki},
  title =	{{An O(n^2 log^2 n) Time Algorithm for Minmax Regret Minsum Sink on Path Networks}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{14:1--14:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.14},
  URN =		{urn:nbn:de:0030-drops-99624},
  doi =		{10.4230/LIPIcs.ISAAC.2018.14},
  annote =	{Keywords: Facility location, minsum sink, evacuation problem, minmax regret, dynamic flow path network}
}
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