License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2018.14
URN: urn:nbn:de:0030-drops-99624
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9962/
Go to the corresponding LIPIcs Volume Portal

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

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

pdf-format:
LIPIcs-ISAAC-2018-14.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{bhattacharya_et_al:LIPIcs:2018:9962,
  author =	{Binay Bhattacharya and Yuya Higashikawa and Tsunehiko Kameda and Naoki Katoh},
  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 =	{Wen-Lian Hsu and Der-Tsai Lee and Chung-Shou Liao},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9962},
  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}
}

Keywords: Facility location, minsum sink, evacuation problem, minmax regret, dynamic flow path network
Collection: 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Issue Date: 2018
Date of publication: 06.12.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI