On the complexity of time-dependent shortest paths. (English) Zbl 1317.68069
Summary: We investigate the complexity of shortest paths in time-dependent graphs where the costs of edges (that is, edge travel times) vary as a function of time, and as a result the shortest path between two nodes \(s\) and \(d\) can change over time. Our main result is that when the edge cost functions are (polynomial-size) piecewise linear, the shortest path from \(s\) to \(d\) can change \(n^{\Theta(\log n)}\) times, settling a several-year-old conjecture of B. C. Dean. However, despite the fact that the arrival time function may have superpolynomial complexity, we show that a minimum delay path for any departure time interval can be computed in polynomial time. We also show that the complexity is polynomial if the slopes of the linear function come from a restricted class and describe an efficient scheme for computing a \((1+\epsilon)\)-approximation of the travel time function.
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 05C35 | Extremal problems in graph theory |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68W25 | Approximation algorithms |
Keywords:
time-dependent shortest path; piecewise linear delay functions; parametric shortest path; approximation algorithmsReferences:
| [1] | Basch, J.; Guibas, L. J.; Hershberger, J., Data structures for mobile data, 747-756 (1997) · Zbl 1321.68213 |
| [2] | Bertsekas, D.P., Tsitsiklis, J.N.: An analysis of stochastic shortest path problems. Math. Oper. Res. 16(3), 580-595 (1991) · Zbl 0751.90077 · doi:10.1287/moor.16.3.580 |
| [3] | Cai, X., Kloks, T., Wong, C.K.: Time-varying shortest path problems with constraints. Networks 29(3), 141-150 (1997) · Zbl 0876.05060 · doi:10.1002/(SICI)1097-0037(199705)29:3<141::AID-NET2>3.0.CO;2-H |
| [4] | Carstensen, P.J.: Parametric cost shortest path problems (1984). Unpublished Bellcore memo · Zbl 0903.90054 |
| [5] | Chabini, I.: Discrete dynamic shortest path problems in transportation applications: complexity and algorithms with optimal run time. J. Transp. Res. Board. 1645, 170-175 (1998) · doi:10.3141/1645-21 |
| [6] | Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, New York (2001) · Zbl 1047.68161 |
| [7] | Dean, B.C.: Continuous-time dynamic shortest path algorithms. Master’s thesis, Massachusetts Institute of Technology (1999) |
| [8] | Dean, B.C.: Shortest paths in FIFO time-dependent networks: theory and algorithms. Technical report (2004) |
| [9] | Dehne, F.; Omran, M. T.; Sack, J.-R., Shortest paths in time-dependent FIFO networks using edge load forecasts, 1-6 (2009) |
| [10] | Dehne, F., Omran, M.T., Sack, J.R.: Shortest paths in time-dependent FIFO networks. Algorithmica, 1-20 (2010) · Zbl 1241.68088 |
| [11] | Delling, D.; Wagner, D., Time-dependent route planning, No. 5868, 207-230 (2009) · Zbl 1266.90039 · doi:10.1007/978-3-642-05465-5_8 |
| [12] | Demetrescu, C., Italiano, G.F.: Dynamic shortest paths and transitive closure: An annotated bibliography (draft) (2005). See www.diku.dk/PATH05/biblio-dynpaths.pdf · Zbl 0172.44202 |
| [13] | Ding, B.; Yu, J. X.; Qin, L., Finding time-dependent shortest paths over large graphs, 205-216 (2008) |
| [14] | Dreyfus, S.E.: An appraisal of some shortest-path algorithms. Oper. Res. 17(3), 395-412 (1969) · Zbl 0172.44202 · doi:10.1287/opre.17.3.395 |
| [15] | Erickson, J., Maximum flows and parametric shortest paths in planar graphs, 794-804 (2010) · Zbl 1288.05055 · doi:10.1137/1.9781611973075.65 |
| [16] | Fernández-Baca, D., Slutzki, G.: Parametric problems on graphs of bounded tree-width. J. Algorithms 16(3), 408-430 (1994) · Zbl 0801.90114 · doi:10.1006/jagm.1994.1019 |
| [17] | Ford, L.R., Fulkerson, D.R.: Flows in Networks. Princeton University Press, Princeton (1962) · Zbl 0106.34802 |
| [18] | Guibas, L. J.; Agarwal, P. K. (ed.); Kavraki, L. E. (ed.); Mason, M. (ed.), Kinetic data structures—a state of the art report, 191-209 (1998) · Zbl 0948.70502 |
| [19] | Gusfield, D.M.: Sensitivity analysis for combinatorial optimization. PhD thesis, University of California, Berkeley (1980) · Zbl 0449.05014 |
| [20] | Kanoulas, E.; Du, Y.; Xia, T.; Zhang, D., Finding fastest paths on a road network with speed patterns, 10 (2006) |
| [21] | Karp, R.M., Orlin, J.B.: Parametric shortest path algorithms with an application to cyclic staffing. Discrete Appl. Math. 3(1), 37-45 (1981) · Zbl 0453.68032 · doi:10.1016/0166-218X(81)90026-3 |
| [22] | King, V., Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs, 81-89 (1999) |
| [23] | Mitchell, J.S.B., Papadimitriou, C.H.: The weighted region problem: finding shortest paths through a weighted planar subdivision. J. ACM 38(1), 18-73 (1991) · Zbl 0799.68150 · doi:10.1145/102782.102784 |
| [24] | Mulmuley, K.; Shah, P., A lower bound for the shortest path problem, 14-21 (2000) · doi:10.1109/CCC.2000.856731 |
| [25] | Nachtigall, K.: Time depending shortest-path problems with applications to railway networks. Eur. J. Oper. Res. 83(1), 154-166 (1995) · Zbl 0903.90054 · doi:10.1016/0377-2217(94)E0349-G |
| [26] | Nannicini, G.; Delling, D.; Liberti, L.; Schultes, D., Bidirectional A∗ search for time-dependent fast paths, No. 5038, 334-346 (2008) · Zbl 1182.90092 · doi:10.1007/978-3-540-68552-4_25 |
| [27] | Nikolova, E.; Brand, M.; Karger, D. R., Optimal route planning under uncertainty (2006) |
| [28] | Nikolova, E.; Kelner, J. A.; Brand, M.; Mitzenmacher, M., Stochastic shortest paths via quasi-convex maximization, 552-563 (2006) · Zbl 1131.05317 |
| [29] | Orda, A., Rom, R.: Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length. J. ACM 37(3), 607-625 (1990) · Zbl 0699.68074 · doi:10.1145/79147.214078 |
| [30] | Roditty, L.; Zwick, U., On dynamic shortest paths problems, No. 3221, 580-591 (2004) · Zbl 1111.68599 |
| [31] | Sherali, H.D., Ozbay, K., Subramanian, S.: The time-dependent shortest pair of disjoint paths problem: complexity, models, and algorithms. Networks 31(4), 259-272 (1998) · Zbl 1002.90077 · doi:10.1002/(SICI)1097-0037(199807)31:4<259::AID-NET6>3.0.CO;2-C |
| [32] | Thorup, M., Worst-case update times for fully-dynamic all-pairs shortest paths, 112-119 (2005) · Zbl 1192.68493 |
| [33] | Young, N., Tarjan, R., Orlin, J.: Faster parametric shortest path and minimum balance algorithms. Networks 21(2), 205-221 (2006) · Zbl 0719.90087 · doi:10.1002/net.3230210206 |
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.
