Minmax regret 1-sink location problems on dynamic flow path networks with parametric weights

Tetsuya Fujie (), Yuya Higashikawa (), Naoki Katoh (), Junichi Teruyama () and Yuki Tokuni ()
Additional contact information
Tetsuya Fujie: University of Hyogo
Yuya Higashikawa: University of Hyogo
Naoki Katoh: University of Hyogo
Junichi Teruyama: University of Hyogo
Yuki Tokuni: University of Hyogo

Journal of Combinatorial Optimization, 2024, vol. 48, issue 2, No 4, 20 pages

Abstract: Abstract This paper addresses the minmax regret 1-sink location problem on a dynamic flow path network with parametric weights. A dynamic flow path network consists of an undirected path with positive edge lengths, positive edge capacities, and nonnegative vertex weights. A path can be considered as a road, an edge length as the distance along the road, and a vertex weight as the number of people at the site. An edge capacity limits the number of people that can enter the edge per unit time. We consider the problem of locating a sink where all the people evacuate quickly. In our model, each weight is represented by a linear function of a common parameter t, and the decision maker who determines the sink location does not know the value of t. We formulate the problem under such uncertainty as the minmax regret problem. Given t and sink location x, the cost is the sum of arrival times at x for all the people determined by t. The regret for x under t is the gap between this cost and the optimal cost under t. The problem is to find the sink location minimizing the maximum regret over all t. For the problem, we propose an $$O(n^4 2^{\alpha (n)} \alpha (n)^2 \log n)$$ O ( n 4 2 α ( n ) α ( n ) 2 log n ) time algorithm, where n is the number of vertices in the network and $$\alpha (\cdot )$$ α ( · ) is the inverse Ackermann function. Also, for the special case in which every edge has the same capacity, we show that the complexity can be reduced to $$O(n^3 2^{\alpha (n)} \alpha (n) \log n)$$ O ( n 3 2 α ( n ) α ( n ) log n ) .

Keywords: Minimax regret; Facility location problem; Polynomial time algorithm; Path network; Dynamic flow (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-024-01199-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:48:y:2024:i:2:d:10.1007_s10878-024-01199-7

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-024-01199-7

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().