2026-08-15T17:32:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9962 2024-03-06T10:45:13Z ddc:004 open_access

An O(n^2 log^2 n) Time Algorithm for Minmax Regret Minsum Sink on Path Networks Bhattacharya, Binay Higashikawa, Yuya Kameda, Tsunehiko Katoh, Naoki Facility location minsum sink evacuation problem minmax regret dynamic flow path network 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Binay Bhattacharya and Yuya Higashikawa and Tsunehiko Kameda and Naoki Katoh 2018 Is Part Of LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2018.14 urn:nbn:de:0030-drops-99624 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.14 eng https://creativecommons.org/licenses/by/3.0/legalcode