PTAS for k-tour cover problem on the plane for moderately large values of k^*

DOI10.1142/S0129054110007623MaRDI QIDQ3069731zbMATHOpenAlexWikidataFDO

Authors Anna Adamaszek, Artur Czumaj, Andrzej Lingas

Publication date 19 January 2011

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0129054110007623

zbMATH Keywords

approximation algorithmspolynomial-time approximation schemecapacitated vehicle routing\(k\)-tour cover

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60) Transportation, logistics and supply chain management (90B06)

Recommendations

• PTAS for \(k\)-tour cover problem on the plane for moderately large values of \(k\)
• scientific article; zbMATH DE number 1559543
• A quasipolynomial time approximation scheme for Euclidean capacitated vehicle routing
• PTAS for the Euclidean capacitated vehicle routing problem in \(\mathbb R^d\)
• A PTAS for MIN-\(k\)-SCCP in Euclidean space of arbitrary fixed dimension

Cites work

• Approximation algorithms for NP-complete problems on planar graphs
• Bounds and Heuristics for Capacitated Routing Problems
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• The truck dispatching problem
• The vehicle routing problem: An overview of exact and approximate algorithms

Cited in

(13)

• Improving the approximation ratio for capacitated vehicle routing
• PTAS for \(k\)-tour cover problem on the plane for moderately large values of \(k\)
• Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension
• scientific article; zbMATH DE number 1559543 (Why is no real title available?)
• Constant-factor approximation algorithms for a series of combinatorial routing problems based on the reduction to the asymmetric traveling salesman problem
• Improving the approximation ratio for capacitated vehicle routing
• Efficient approximation of the capacitated vehicle routing problem in a metric space of an arbitrary fixed doubling dimension
• Local search algorithms for multiple-depot vehicle routing and for multiple traveling salesman problems with proved performance guarantees
• A PTAS for MIN-\(k\)-SCCP in Euclidean space of arbitrary fixed dimension
• Approximation of the capacitated vehicle routing problem with a limited number of routes in metric spaces of fixed doubling dimension
• A PTAS for Capacitated Vehicle Routing on Trees
• Iterated tour partitioning for Euclidean capacitated vehicle routing
• Efficient approximation of the metric CVRP in spaces of fixed doubling dimension

Describes a project that uses

Uses Software

• VRP

This page was built for publication: PTAS for \(k\)-tour cover problem on the plane for moderately large values of \(k^*\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3069731)