A fast \((2 + \frac{2}{7})\)-approximation algorithm for capacitated cycle covering
From MaRDI portal
Publication:2118143
DOI10.1007/s10107-021-01678-3OpenAlexW3176143293MaRDI QIDQ2118143
Publication date: 22 March 2022
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-021-01678-3
Linear programming (90C05) Transportation, logistics and supply chain management (90B06) Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20)
Uses Software
Cites Work
- Improved approximation algorithms for some min-max and minimum cycle cover problems
- A quasipolynomial time approximation scheme for Euclidean capacitated vehicle routing
- Min-max tree covers of graphs.
- Improved bounds for vehicle routing solutions
- Heuristics for unequal weight delivery problems with a fixed error guarantee
- On the complexity of the separation problem for rounded capacity inequalities
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- On the Held-Karp relaxation for the asymmetric and symmetric traveling salesman problems
- Worst-case comparison of valid inequalities for the TSP
- A PTAS for bounded-capacity vehicle routing in planar graphs
- A generic exact solver for Vehicle Routing and related problems
- Improved branch-cut-and-price for capacitated vehicle routing
- Better approximability results for min-max tree/cycle/path cover problems
- A unified solution framework for multi-attribute vehicle routing problems
- The Truck Dispatching Problem
- PTAS for the Euclidean Capacitated Vehicle Routing Problem in $$R^d$$
- Bounds and Heuristics for Capacitated Routing Problems
- Capacitated Vehicle Routing on Trees
- Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Improving the approximation ratio for capacitated vehicle routing
- New approximation algorithms for the minimum cycle cover problem
