A quasi-polynomial-time approximation scheme for vehicle routing on planar and bounded-genus graphs

DOI10.4230/LIPICS.ESA.2017.12MaRDI QIDQ5111697zbMATH OpenOpenAlexFDO

Authors 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

zbMATH Keywords

approximation algorithmsplanar graphscapacitated vehicle routing

Mathematics Subject Classification ID

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)

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

Cites work

• scientific article; zbMATH DE number 1303035 (Why is no real title available?)
• scientific article; zbMATH DE number 1303538 (Why is no real title available?)
• scientific article; zbMATH DE number 1306896 (Why is no real title available?)
• scientific article; zbMATH DE number 2079390 (Why is no real title available?)
• scientific article; zbMATH DE number 1559543 (Why is no real title available?)
• A new approximation algorithm for the capacitated vehicle routing problem on a tree
• A quasipolynomial time approximation scheme for Euclidean capacitated vehicle routing
• Approximating \(k\)-center in planar graphs
• Approximating connectivity domination in weighted bounded-genus graphs
• Bounds and Heuristics for Capacitated Routing Problems
• Capacitated arc routing problems
• Compact oracles for reachability and approximate distances in planar digraphs
• PTAS for \(k\)-tour cover problem on the plane for moderately large values of \(k\)
• PTAS for the Euclidean capacitated vehicle routing problem in \(\mathbb R^d\)
• Polynomial time approximation scheme for single-depot Euclidean capacitated vehicle routing problem

Cited in

(7)

• 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.
• A quasipolynomial time approximation scheme for Euclidean capacitated vehicle routing
• 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

Describes a project that uses

Uses Software

• VRP

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)