Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension
From MaRDI portal
Publication:5009565
Recommendations
- Approximation Schemes for Capacitated Vehicle Routing on Graphs of Bounded Treewidth, Bounded Doubling, or Highway Dimension
- scientific article; zbMATH DE number 6297716
- The capacitated vehicle routing problem: stronger bounds in pseudo-polynomial time
- A quasipolynomial time approximation scheme for Euclidean capacitated vehicle routing
- Fixed-parameter approximations for \(k\)-center problems in low highway dimension graphs
- Fixed parameter approximations for \(k\)-center problems in low highway dimension graphs
- Efficient approximation of the capacitated vehicle routing problem in a metric space of an arbitrary fixed doubling dimension
- Polynomial-time approximation scheme for the capacitated vehicle routing problem with time windows
- Approximation of the capacitated vehicle routing problem with a limited number of routes in metric spaces of fixed doubling dimension
- Polynomial time approximation scheme for single-depot Euclidean capacitated vehicle routing problem
Cites work
- A $$(1+{\varepsilon })$$ ( 1 + ε ) -Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
- A Best Possible Heuristic for the k-Center Problem
- A new approximation algorithm for the capacitated vehicle routing problem on a tree
- A quasi-polynomial-time approximation scheme for vehicle routing on planar and bounded-genus graphs
- A quasipolynomial time approximation scheme for Euclidean capacitated vehicle routing
- An Improved Approximation for k -Median and Positive Correlation in Budgeted Optimization
- Approximate clustering via core-sets
- Bounds and Heuristics for Capacitated Routing Problems
- Capacitated arc routing problems
- Clustering to minimize the maximum intercluster distance
- Fixed parameter approximations for \(k\)-center problems in low highway dimension graphs
- Greedy Strikes Back: Improved Facility Location Algorithms
- Highway dimension and provably efficient shortest path algorithms
- Highway dimension, shortest paths, and provably efficient algorithms
- scientific article; zbMATH DE number 5734726 (Why is no real title available?)
- scientific article; zbMATH DE number 1303035 (Why is no real title available?)
- scientific article; zbMATH DE number 2079382 (Why is no real title available?)
- scientific article; zbMATH DE number 1559543 (Why is no real title available?)
- scientific article; zbMATH DE number 1775394 (Why is no real title available?)
- Local Search Heuristics for k-Median and Facility Location Problems
- Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics
- PTAS for k-tour cover problem on the plane for moderately large values of k^*
- VC-dimension and shortest path algorithms
Cited in
(20)- On the VC-dimension of unique round-trip shortest path systems
- \(\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
- Improved approximations for capacitated vehicle routing with unsplittable client demands
- The parameterized hardness of the \(k\)-center problem in transportation networks
- Polynomial time approximation schemes for clustering in low highway dimension graphs
- Computing constrained shortest-paths at scale
- A fast (2 + 2/7)-approximation algorithm for capacitated cycle covering
- Polynomial time approximation schemes for clustering in low highway dimension graphs
- Improving the approximation ratio for capacitated vehicle routing
- Travelling on graphs with small highway dimension
- Improving the approximation ratio for capacitated vehicle routing
- 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
- Fixed-parameter approximations for \(k\)-center problems in low highway dimension graphs
- Improved approximations for the capacitated vehicle routing problem with fixed capacity
- Generalized k-center: distinguishing doubling and highway dimension
- On sparse hitting sets: from fair vertex cover to highway dimension
- Euclidean capacitated vehicle routing in the random setting: a 1.55-approximation algorithm
This page was built for publication: Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5009565)
