Parametric Shortest-Path Algorithms via Tropical Geometry

References

• [1] Aho AV, Hopcroft JE, Ullman JD (1975) The Design and Analysis of Computer Algorithms (Addison-Wesley, Reading, MA).Google Scholar
• [2] Akian M, Gaubert S, Guterman A (2012) Tropical polyhedra are equivalent to mean payoff games. Internat. J. Algebra Comput. 22(1):1250001.Crossref, Google Scholar
• [3] Allamigeon X, Benchimol P, Gaubert S, Joswig M (2018) Log-barrier interior point methods are not strongly polynomial. SIAM J. Appl. Algebra Geometry 2(1):140–178.Crossref, Google Scholar
• [4] Alon N, Awerbuch B, Azar Y, Buchbinder N, Naor J (2006) A general approach to online network optimization problems. ACM Trans. Algorithms 2(4):640–660.Crossref, Google Scholar
• [5] Assarf B, Gawrilow E, Herr K, Joswig M, Lorenz B, Paffenholz A, Rehn T (2017) Computing convex hulls and counting integer points with polymake. Math. Programming Comput. 9(1):1–38.Crossref, Google Scholar
• [6] Ben-Tal A, El Ghaoui L, Nemirovski A (2009) Robust Optimization (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• [7] Bernstein A (2016) Maintaining shortest paths under deletions in weighted directed graphs. SIAM J. Comput. 45(2):548–574.Crossref, Google Scholar
• [8] Butkovič P (2010) Max-Linear Systems: Theory and Algorithms (Springer, London).Crossref, Google Scholar
• [9] Chassein A, Dokka T, Goerigk M (2019) Algorithms and uncertainty sets for data-driven robust shortest path problems. Eur. J. Oper. Res. 274(2):671–686.Crossref, Google Scholar
• [10] Ellson J, Gansner E, Hu Y, Janssen E, North S, Jacobsson M, Fernandez M, et al. (2021) Graphviz version 2.49.3. www.graphviz.org.Google Scholar
• [11] Fredman ML (1976) New bounds on the complexity of the shortest path problem. SIAM J. Comput. 5(1):83–89.Crossref, Google Scholar
• [12] Fredman ML, Tarjan RE (1987) Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34(3):596–615.Crossref, Google Scholar
• [13] Gallo G, Grigoriadis MD, Tarjan RE (1989) A fast parametric maximum flow algorithm and applications. SIAM J. Comput. 18(1):30–55.Crossref, Google Scholar
• [14] Gawrilow E, Joswig M (2000) Polymake: A framework for analyzing convex polytopes. Kalai G, Ziegler GM, eds. Polytopes—Combinatorics and Computation (Birkhäuser, Basel, Switzerland), 43–73.Crossref, Google Scholar
• [15] Gawrilow E, Köhler E, Möhring RH, Stenzel B (2008) Dynamic routing of automated guided vehicles in real-time. Krebs H-J, Jäger W, eds. Mathematics—Key Technology for the Future (Springer, Berlin), 165–177.Crossref, Google Scholar
• [16] Goldberg AV, Tarjan RE (1988) A new approach to the maximum-flow problem. J. ACM 35(4):921–940.Crossref, Google Scholar
• [17] Grötschel M, Lovász L, Schrijver A (1993) Geometric Algorithms and Combinatorial Optimization, 2nd ed. (Springer, Berlin).Crossref, Google Scholar
• [18] Han Y, Takaoka T (2016) An O (n3log log n/log 2n) time algorithm for all pairs shortest paths. J. Discrete Algorithms 38–41:9–19.Crossref, Google Scholar
• [19] Jahn O, Möhring RH, Schulz AS, Stier-Moses NE (2005) System-optimal routing of traffic flows with user constraints in networks with congestion. Oper. Res. 53(4):600–616.Link, Google Scholar
• [20] Joswig M, Loho G (2020) Monomial tropical cones for multicriteria optimization. SIAM J. Discrete Math. 34(2):1172–1191.Crossref, Google Scholar
• [21] Maclagan D, Sturmfels B (2015) Introduction to Tropical Geometry (American Mathematical Society, Providence, RI).Crossref, Google Scholar
• [22] Matuschke J, Skutella M, Soto J (2015) Robust randomized matchings. Proc. 26th Annual ACM-SIAM Sympos. Discrete Algorithms (SODA 2015) (ACM, New York), 1904–1915.Google Scholar
• [23] Schrijver A (2003) Combinatorial Optimization: Polyhedra and Efficiency, vol. A (Springer, Berlin).Google Scholar
• [24] Tarjan RE (1983) Data Structures and Network Algorithms (SIAM, Philadelphia).Crossref, Google Scholar
• [25] Tran NM (2017) Enumerating polytropes. J. Combin. Theory Ser. A 151:1–22.Crossref, Google Scholar
• [26] Transportation Networks for Research Core Team (2018) Transportation networks for research. Retrieved August 14, https://github.com/bstabler/TransportationNetworks.Google Scholar
• [27] Yu G, Yang J (1998) On the robust shortest path problem. Comput. Oper. Res. 25(6):457–468.Crossref, Google Scholar