Parametric Shortest-Path Algorithms via Tropical Geometry
From MaRDI portal
Publication:5868948
DOI10.1287/moor.2021.1199OpenAlexW3097750129WikidataQ114058155 ScholiaQ114058155MaRDI QIDQ5868948
Benjamin Schröter, Michael Joswig
Publication date: 26 September 2022
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1904.01082
Programming involving graphs or networks (90C35) Sensitivity, stability, parametric optimization (90C31) Graph theory (including graph drawing) in computer science (68R10) Transportation, logistics and supply chain management (90B06) Traffic problems in operations research (90B20) Distance in graphs (05C12) Applications of tropical geometry (14T90) Tropical optimization (e.g., max-plus optimization) (90C24)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Enumerating Polytropes
- An \(O(n^3 \log \log n / \log^2 n)\) time algorithm for all pairs shortest paths
- Geometric algorithms and combinatorial optimization.
- On the robust shortest path problem.
- Algorithms and uncertainty sets for data-driven robust shortest path problems
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Computing convex hulls and counting integer points with \texttt{polymake}
- Maintaining Shortest Paths Under Deletions in Weighted Directed Graphs
- TROPICAL POLYHEDRA ARE EQUIVALENT TO MEAN PAYOFF GAMES
- A general approach to online network optimization problems
- Max-linear Systems: Theory and Algorithms
- A new approach to the maximum-flow problem
- New Bounds on the Complexity of the Shortest Path Problem
- Log-Barrier Interior Point Methods Are Not Strongly Polynomial
- A Fast Parametric Maximum Flow Algorithm and Applications
- Monomial Tropical Cones for Multicriteria Optimization
- Fibonacci heaps and their uses in improved network optimization algorithms
- System-Optimal Routing of Traffic Flows with User Constraints in Networks with Congestion
- Robust randomized matchings
