Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension
From MaRDI portal
Publication:5009565
DOI10.4230/LIPIcs.ESA.2018.8OpenAlexW2889438244MaRDI QIDQ5009565
David Saulpic, Amariah Becker, Philip N. Klein
Publication date: 4 August 2021
Full work available at URL: https://arxiv.org/abs/1707.08270
Related Items
A Fast $$(2 + 2/7)$$-Approximation Algorithm for Capacitated Cycle Covering ⋮ Improved approximations for capacitated vehicle routing with unsplittable client demands ⋮ The parameterized hardness of the \(k\)-center problem in transportation networks ⋮ Generalized \(k\)-center: distinguishing doubling and highway dimension ⋮ A PTAS for Capacitated Vehicle Routing on Trees ⋮ Approximation Schemes for Capacitated Vehicle Routing on Graphs of Bounded Treewidth, Bounded Doubling, or Highway Dimension ⋮ On the VC-dimension of unique round-trip shortest path systems ⋮ Polynomial time approximation schemes for clustering in low highway dimension graphs ⋮ Fixed-parameter approximations for \(k\)-center problems in low highway dimension graphs ⋮ Improving the approximation ratio for capacitated vehicle routing ⋮ Improving the approximation ratio for capacitated vehicle routing ⋮ Travelling on graphs with small highway dimension ⋮ \(\mathsf{W[1}\)-hardness of the \(k\)-center problem parameterized by the skeleton dimension] ⋮ A fast \((2 + \frac{2}{7})\)-approximation algorithm for capacitated cycle covering ⋮ Computing Constrained Shortest-Paths at Scale
Uses Software
Cites Work
- A quasipolynomial time approximation scheme for Euclidean capacitated vehicle routing
- Clustering to minimize the maximum intercluster distance
- VC-Dimension and Shortest Path Algorithms
- PTAS FOR k-TOUR COVER PROBLEM ON THE PLANE FOR MODERATELY LARGE VALUES OF k
- Highway Dimension and Provably Efficient Shortest Path Algorithms
- A $$(1+{\varepsilon })$$ ( 1 + ε ) -Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
- Fixed Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs
- Approximate clustering via core-sets
- A Best Possible Heuristic for the k-Center Problem
- Bounds and Heuristics for Capacitated Routing Problems
- Capacitated arc routing problems
- Greedy Strikes Back: Improved Facility Location Algorithms
- Local Search Yields Approximation Schemes for $k$-Means and $k$-Median in Euclidean and Minor-Free Metrics
- Local Search Heuristics for k-Median and Facility Location Problems
- An Improved Approximation for k -Median and Positive Correlation in Budgeted Optimization
- A Quasi-Polynomial-Time Approximation Scheme for Vehicle Routing on Planar and Bounded-Genus Graphs
- A new approximation algorithm for the capacitated vehicle routing problem on a tree
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
