The universally quickest transshipment problem in a certain class of dynamic networks with uniform path-lengths. (English) Zbl 1303.90014
Summary: In the universally quickest transshipment problem, we are given a network with a transit time function on its arc set. The goal is to minimize the time when the last supply reaches the sink and to maximize the amount of supplies which have reached the sink at every time step. In this paper, we consider this problem in a class of dynamic networks which is a generalization of grid networks with uniform capacity and uniform transit time, and present a polynomial-time algorithm for this case.
MSC:
| 90B10 | Deterministic network models in operations research |
| 90B20 | Traffic problems in operations research |
References:
| [1] | Ahuja, R. K.; Magnanti, T. L.; Orlin, J. B., Network Flows: Theory, Algorithm, and Applications (1993), Prentice Hall · Zbl 1201.90001 |
| [2] | Baumann, N.; Skutella, M., Earliest arrival flows with multiple sources, Math. Oper. Res., 34, 2, 499-512 (2009) · Zbl 1218.90166 |
| [3] | Fleischer, L., Faster algorithms for the quickest transshipment problem, SIAM J. Optim., 12, 1, 18-35 (2001) · Zbl 0992.68071 |
| [4] | Fleischer, L.; Skutella, M., Quickest flows over time, SIAM J. Comput., 36, 6, 1600-1630 (2007) · Zbl 1146.90014 |
| [5] | Ford, L. R.; Fulkerson, D. R., Flows in Networks (1962), Princeton University Press · Zbl 0106.34802 |
| [6] | Fujishige, S., Lexicographically optimal base of a polymatroid with respect to a weight vector, Math. Oper. Res., 5, 186-196 (1980) · Zbl 0442.90071 |
| [7] | Gallo, G.; Grigoriadis, M. D.; Tarjan, R. E., A fast parametric maximum flow algorithm and applications, SIAM J. Comput., 18, 1, 30-55 (1989) · Zbl 0679.68080 |
| [8] | Goldberg, A. V.; Tarjan, R. E., A new approach to the maximum-flow problem, J. ACM, 35, 4, 921-940 (1988) · Zbl 0661.90031 |
| [9] | Hajek, B.; Ogier, R. G., Optimal dynamic routing in communication networks with continuous traffic, Networks, 14, 457-487 (1984) · Zbl 0546.90097 |
| [10] | Hall, A.; Hippler, S.; Skutella, M., Multicommodity flows over time: efficient algorithms and complexity, Theoret. Comput. Sci., 379, 3, 387-404 (2007) · Zbl 1149.90032 |
| [11] | Hamacher, H. W.; Tjandra, S. A., Mathematical modelling of evacuation problem: state of the art, (Schreckenberg, M.; Sharma, S. D., Pedestrian and Evacuation Dynamics (2002), Springer), 227-266 · Zbl 1048.90041 |
| [12] | Hoppe, B.; Tardos, É., The quickest transshipment problem, Math. Oper. Res., 25, 1, 36-62 (2000) · Zbl 0977.90002 |
| [13] | Jarvis, J. J.; Ratliff, D., Some equivalent objectives for dynamic network flow problems, Manag. Sci., 28, 1, 106-109 (1982) · Zbl 0486.90042 |
| [14] | Kamiyama, N.; Katoh, N., The minimum weight in-tree cover problem, (Proceeding of the Second International Conference on Modelling, Comput. and Optimization in Information Systems and Management Sciences. Proceeding of the Second International Conference on Modelling, Comput. and Optimization in Information Systems and Management Sciences, Communications in Computer and Information Science, vol. 14 (2008)), 155-164 · Zbl 1160.90677 |
| [15] | Kamiyama, N.; Katoh, N.; Takizawa, A., An efficient algorithm for evacuation problem in dynamic network flows with uniform arc capacity, IEICE Trans. Inf. Syst., E89-D, 8, 2372-2379 (2006) |
| [16] | Kamiyama, N.; Katoh, N.; Takizawa, A., An efficient algorithm for the evacuation problem in a certain class of networks with uniform path-lengths, Discrete Appl. Math., 157, 17, 3665-3677 (2009) · Zbl 1228.90018 |
| [17] | Mamada, S.; Uno, T.; Makino, K.; Fujishige, S., An \(O(n \log^2 n)\) algorithm for the optimal sink location problem in dynamic tree networks, Discrete Appl. Math., 154, 16, 2387-2401 (2006) · Zbl 1130.90029 |
| [18] | Megiddo, N., A good algorithm for lexicographically optimal flows in multi-terminal networks, Bull. Amer. Math. Soc., 83, 3 (1977) · Zbl 0354.90083 |
| [19] | Megiddo, N., Optimal flows in networks with multiple sources and sinks, Math. Program., 7, 97-107 (1974) · Zbl 0296.90048 |
| [20] | Minieka, E., Maximal, lexicographic, and dynamic network flows, Oper. Res., 21, 517-527 (1973) · Zbl 0307.90025 |
| [21] | Schrijver, A., Combinatorial Optimization: Polyhedra and Efficiency (2003), Springer · Zbl 1041.90001 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
