PTAS for k-tour cover problem on the plane for moderately large values of k^*
DOI10.1142/S0129054110007623zbMATH Open1207.90013OpenAlexW2568219823WikidataQ58203697 ScholiaQ58203697MaRDI QIDQ3069731FDOQ3069731
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
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
approximation algorithmspolynomial-time approximation schemecapacitated vehicle routing\(k\)-tour cover
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)
Cites Work
- The vehicle routing problem: An overview of exact and approximate algorithms
- The truck dispatching problem
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- 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
Cited In (13)
- PTAS for \(k\)-tour cover problem on the plane for moderately large values of \(k\)
- A PTAS for Capacitated Vehicle Routing on Trees
- Efficient approximation of the metric CVRP in spaces of fixed doubling dimension
- A PTAS for MIN-\(k\)-SCCP in Euclidean space of arbitrary fixed dimension
- Improving the approximation ratio for capacitated vehicle routing
- Approximation of the capacitated vehicle routing problem with a limited number of routes in metric spaces of fixed doubling dimension
- Local search algorithms for multiple-depot vehicle routing and for multiple traveling salesman problems with proved performance guarantees
- Efficient approximation of the capacitated vehicle routing problem in a metric space of an arbitrary fixed doubling dimension
- Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension
- Constant-factor approximation algorithms for a series of combinatorial routing problems based on the reduction to the asymmetric traveling salesman problem
- Title not available (Why is that?)
- Improving the approximation ratio for capacitated vehicle routing
- Iterated tour partitioning for Euclidean capacitated vehicle routing
Uses Software
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)
