Abstract
This paper addresses the minmax regret 1-sink location problem on dynamic flow path networks with parametric weights. We are given a dynamic flow network consisting 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 in the network, to which all the people evacuate from the vertices as quickly as possible. In our model, each weight is represented by a linear function in a common parameter t, and the decision maker who determines the location of a sink does not know the value of t. We formulate the sink location problem under such uncertainty as the minmax regret problem. Given t and a sink location x, the cost of x under t 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 the cost of x under t and the optimal cost under t. The task of the problem is formulated as the one to find a sink location that minimizes the maximum regret over all t. For the problem, we propose an \(O(n^4 2^{\alpha (n)} \alpha (n) \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)\).
A full version of the paper is available at [13]; https://arxiv.org/abs/2011.13569.
This work is supported by JSPS KAKENHI Grant-in-Aid for Early-Career Scientists (18K18003, 20K19746), JSPS KAKENHI Grant-in-Aid for Scientific Research (B) (19H04068), and JST CREST (JPMJCR1402).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Agarwal, P.K., Sharir, M., Shor, P.: Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences. J. Comb. Theory Ser. A 52(2), 228–274 (1989)
Alstrup, S., Gavoille, C., Kaplan, H., Rauhe, T.: Nearest common ancestors: a survey and a new distributed algorithm. In: Proceedings of the 14th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA 2002), pp. 258–264 (2002)
Arumugam, G.P., Augustine, J., Golin, M.J., Srikanthan, P.: Minmax regret \(k\)-sink location on a dynamic path network with uniform capacities. Algorithmica 81(9), 3534–3585 (2019)
Bender, M.A., Farach-Colton, M.: The LCA problem revisited. In: Gonnet, G.H., Viola, A. (eds.) LATIN 2000. LNCS, vol. 1776, pp. 88–94. Springer, Heidelberg (2000). https://doi.org/10.1007/10719839_9
Benkoczi, R., Bhattacharya, B., Higashikawa, Y., Kameda, T., Katoh, N.: Minsum k-sink problem on dynamic flow path networks. In: Iliopoulos, C., Leong, H.W., Sung, W.-K. (eds.) IWOCA 2018. LNCS, vol. 10979, pp. 78–89. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-94667-2_7
Benkoczi, R., Bhattacharya, B., Higashikawa, Y., Kameda, T., Katoh, N.: Minsum \(k\)-sink problem on path networks. Theor. Comput. Sci. 806, 388–401 (2020)
Bhattacharya, B., Golin, M.J., Higashikawa, Y., Kameda, T., Katoh, N.: Improved algorithms for computing k-sink on dynamic flow path networks. In: Ellen, F., Kolokolova, A., Sack, J.R. (eds.) WADS 2017. LNCS, vol. 10389, pp. 133–144. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-62127-2_12
Bhattacharya, B., Higashikawa, Y., Kameda, T., Katoh, N.: An \({O}(n^2 \log ^2 n)\) time algorithm for minmax regret minsum sink on path networks. In: Proceedings of the 29th International Symposium on Algorithms and Computation 2018 (2018)
Bhattacharya, B., Kameda, T.: Improved algorithms for computing minmax regret sinks on dynamic path and tree networks. Theor. Comput. Sci. 607, 411–425 (2015)
Chen, D., Golin, M.J.: Sink evacuation on trees with dynamic confluent flows. In: 27th International Symposium on Algorithms and Computation (2016)
Chen, D., Golin, M.J.: Minmax centered k-partitioning of trees and applications to sink evacuation with dynamic confluent flows. CoRR abs/1803.09289 (2018)
Ford, L.R., Fulkerson, D.R.: Constructing maximal dynamic flows from static flows. Oper. Res. 6(3), 419–433 (1958)
Fujie, T., Higashikawa, Y., Katoh, N., Teruyama, J., Tokuni, Y.: Minmax regret 1-sink location problems on dynamic flow path networks with parametric weights. CoRR abs/2011.13569 (2020)
Golin, M.J., Sandeep, S.: Minmax-regret \(k\)-sink location on a dynamic tree network with uniform capacities. CoRR abs/1806.03814 (2018)
Hart, S., Sharir, M.: Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes. Combinatorica 6(2), 151–177 (1986)
Hershberger, J.: Finding the upper envelope of \(n\) line segments in \({O}(n \log n)\) time. Inf. Process. Lett. 33(4), 169–174 (1989)
Higashikawa, Y.: Studies on the space exploration and the sink location under incomplete information towards applications to evacuation planning. Ph.D. thesis, Kyoto University, Japan (2014)
Higashikawa, Y., et al.: Minimax regret 1-sink location problem in dynamic path networks. Theor. Comput. Sci. 588, 24–36 (2015)
Higashikawa, Y., Cheng, S.W., Kameda, T., Katoh, N., Saburi, S.: Minimax regret 1-median problem in dynamic path networks. Theory Comput. Syst. 62(6), 1392–1408 (2018)
Higashikawa, Y., Golin, M.J., Katoh, N.: Minimax regret sink location problem in dynamic tree networks with uniform capacity. J. Graph Algorithms Appl. 18(4), 539–555 (2014)
Higashikawa, Y., Golin, M.J., Katoh, N.: Multiple sink location problems in dynamic path networks. Theor. Comput. Sci. 607, 2–15 (2015)
Hoppe, B., Tardos, E.: The quickest transshipment problem. Math. Oper. Res. 25(1), 36–62 (2000)
Kouvelis, P., Yu, G.: Robust Discrete Optimization and its Applications. Kluwer Academic Publishers, London (1997)
Li, H., Xu, Y.: Minimax regret 1-sink location problem with accessibility in dynamic general networks. Eur. J. Oper. Res. 250(2), 360–366 (2016)
Li, H., Xu, Y., Ni, G.: Minimax regret vertex 2-sink location problem in dynamic path networks. J. Comb. Optim. 31(1), 79–94 (2014). https://doi.org/10.1007/s10878-014-9716-2
Mamada, S., Uno, T., Makino, K., Fujishige, S.: An \({O}(n \log ^2 n)\) algorithm for a sink location problem in dynamic tree networks. Discret. Appl. Math. 154, 2387–2401 (2006)
Skutella, M.: An introduction to network flows over time. In: Cook, W., Lovász, L., Vygen, J. (eds.) Research Trends in Combinatorial Optimization, pp. 451–482. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-540-76796-1_21
Vairaktarakis, G.L., Kouvelis, P.: Incorporation dynamic aspects and uncertainty in 1-median location problems. Nav. Res. Logist. (NRL) 46(2), 147–168 (1999)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Fujie, T., Higashikawa, Y., Katoh, N., Teruyama, J., Tokuni, Y. (2021). Minmax Regret 1-Sink Location Problems on Dynamic Flow Path Networks with Parametric Weights. In: Uehara, R., Hong, SH., Nandy, S.C. (eds) WALCOM: Algorithms and Computation. WALCOM 2021. Lecture Notes in Computer Science(), vol 12635. Springer, Cham. https://doi.org/10.1007/978-3-030-68211-8_5
Download citation
DOI: https://doi.org/10.1007/978-3-030-68211-8_5
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-68210-1
Online ISBN: 978-3-030-68211-8
eBook Packages: Computer ScienceComputer Science (R0)