A quasi-polynomial-time approximation scheme for vehicle routing on planar and bounded-genus graphs
DOI10.4230/LIPICS.ESA.2017.12zbMATH Open1442.90192OpenAlexW2966058519MaRDI QIDQ5111697FDOQ5111697
Philip N. Klein, Amariah Becker, David Saulpic
Publication date: 27 May 2020
Full work available at URL: http://drops.dagstuhl.de/opus/volltexte/2017/7878/pdf/LIPIcs-ESA-2017-12.pdf
Recommendations
- scientific article; zbMATH DE number 6297716
- A quasipolynomial time approximation scheme for Euclidean capacitated vehicle routing
- Polynomial time approximation scheme for single-depot Euclidean capacitated vehicle routing problem
- Approximation of the capacitated vehicle routing problem with a limited number of routes in metric spaces of fixed doubling dimension
- Improved polynomial time approximation scheme for capacitated vehicle routing problem with time windows
Programming involving graphs or networks (90C35) Approximation algorithms (68W25) Planar graphs; geometric and topological aspects of graph theory (05C10) Traffic problems in operations research (90B20)
Cites Work
- Bounds and Heuristics for Capacitated Routing Problems
- Capacitated arc routing problems
- Compact oracles for reachability and approximate distances in planar digraphs
- A new approximation algorithm for the capacitated vehicle routing problem on a tree
- A quasipolynomial time approximation scheme for Euclidean capacitated vehicle routing
- PTAS for \(k\)-tour cover problem on the plane for moderately large values of \(k\)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Approximating k-center in planar graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Polynomial Time Approximation Scheme for Single-Depot Euclidean Capacitated Vehicle Routing Problem
- Approximating connectivity domination in weighted bounded-genus graphs
- Title not available (Why is that?)
- PTAS for the Euclidean Capacitated Vehicle Routing Problem in $$R^d$$
Cited In (6)
- A PTAS for Capacitated Vehicle Routing on Trees
- A PTAS for bounded-capacity vehicle routing in planar graphs
- Stronger ILPs for the Graph Genus Problem.
- Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension
- Improved approximations for capacitated vehicle routing with unsplittable client demands
- Approximation Schemes for Capacitated Vehicle Routing on Graphs of Bounded Treewidth, Bounded Doubling, or Highway Dimension
Uses Software
This page was built for publication: A quasi-polynomial-time approximation scheme for vehicle routing on planar and bounded-genus graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111697)
