A Quasi-Polynomial-Time Approximation Scheme for Vehicle Routing on Planar and Bounded-Genus Graphs
From MaRDI portal
Publication:5111697
DOI10.4230/LIPIcs.ESA.2017.12zbMath1442.90192OpenAlexW2966058519MaRDI QIDQ5111697
Amariah Becker, David Saulpic, Philip N. Klein
Publication date: 27 May 2020
Full work available at URL: http://drops.dagstuhl.de/opus/volltexte/2017/7878/pdf/LIPIcs-ESA-2017-12.pdf
Programming involving graphs or networks (90C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Traffic problems in operations research (90B20) Approximation algorithms (68W25)
Related Items (5)
Improved approximations for capacitated vehicle routing with unsplittable client demands ⋮ A PTAS for Capacitated Vehicle Routing on Trees ⋮ Approximation Schemes for Capacitated Vehicle Routing on Graphs of Bounded Treewidth, Bounded Doubling, or Highway Dimension ⋮ Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension ⋮ Stronger ILPs for the Graph Genus Problem.
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A quasipolynomial time approximation scheme for Euclidean capacitated vehicle routing
- PTAS for the Euclidean Capacitated Vehicle Routing Problem in $$R^d$$
- Polynomial Time Approximation Scheme for Single-Depot Euclidean Capacitated Vehicle Routing Problem
- PTAS for k-Tour Cover Problem on the Plane for Moderately Large Values of k
- Bounds and Heuristics for Capacitated Routing Problems
- Capacitated arc routing problems
- Approximating connectivity domination in weighted bounded-genus graphs
- Approximating k-center in planar graphs
- Compact oracles for reachability and approximate distances in planar digraphs
- A new approximation algorithm for the capacitated vehicle routing problem on a tree
This page was built for publication: A Quasi-Polynomial-Time Approximation Scheme for Vehicle Routing on Planar and Bounded-Genus Graphs
