PTAS FOR k-TOUR COVER PROBLEM ON THE PLANE FOR MODERATELY LARGE VALUES OF k

DOI10.1142/S0129054110007623zbMath1207.90013OpenAlexW2568219823WikidataQ58203697 ScholiaQ58203697MaRDI QIDQ3069731

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

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

Related Items (10)

A PTAS for Capacitated Vehicle Routing on Trees ⋮ Iterated tour partitioning for Euclidean capacitated vehicle routing ⋮ Constant-factor approximation algorithms for a series of combinatorial routing problems based on the reduction to the asymmetric traveling salesman problem ⋮ Local search algorithms for multiple-depot vehicle routing and for multiple traveling salesman problems with proved performance guarantees ⋮ Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension ⋮ Efficient approximation of the capacitated vehicle routing problem in a metric space of an arbitrary fixed doubling dimension ⋮ Improving the approximation ratio for capacitated vehicle routing ⋮ Efficient approximation of the metric CVRP in spaces of fixed doubling 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

Uses Software

• VRP

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
• 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
• Approximation algorithms for NP-complete problems on planar graphs

This page was built for publication: PTAS FOR k-TOUR COVER PROBLEM ON THE PLANE FOR MODERATELY LARGE VALUES OF k