Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension (Q5009565): Difference between revisions

Latest revision as of 09:01, 30 July 2024

scientific article; zbMATH DE number 7378678

Language	Label	Description	Also known as
English	Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension	scientific article; zbMATH DE number 7378678

Statements

0 references

0 references

0 references

0 references

4 August 2021

0 references

full work available at URL

https://arxiv.org/abs/1707.08270

0 references

zbMATH Keywords

highway dimension

0 references

capacitated vehicle routing

0 references

graph embeddings

0 references

describes a project that uses

DIMACS

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

VC-Dimension and Shortest Path Algorithms

0 references

Highway Dimension and Provably Efficient Shortest Path Algorithms

0 references

Q5417667

0 references

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

0 references

Q4542527

0 references

Local Search Heuristics for k-Median and Facility Location Problems

0 references

A new approximation algorithm for the capacitated vehicle routing problem on a tree

0 references

Q4526992

0 references

Approximate clustering via core-sets

0 references

Q3574266

0 references

A Quasi-Polynomial-Time Approximation Scheme for Vehicle Routing on Planar and Bounded-Genus Graphs

0 references

An Improved Approximation for k -Median and Positive Correlation in Budgeted Optimization

0 references

Local Search Yields Approximation Schemes for $k$-Means and $k$-Median in Euclidean and Minor-Free Metrics

0 references

A quasipolynomial time approximation scheme for Euclidean capacitated vehicle routing

0 references

Fixed Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs

0 references

A $$(1+{\varepsilon })$$ ( 1 + ε ) -Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs

0 references

Capacitated arc routing problems

0 references

Clustering to minimize the maximum intercluster distance

0 references

Greedy Strikes Back: Improved Facility Location Algorithms

0 references

Q4471341

0 references

Bounds and Heuristics for Capacitated Routing Problems

0 references

Q4249536

0 references

A Best Possible Heuristic for the k-Center Problem

0 references

title

Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension (English)

0 references

Identifiers

DOI

10.4230/LIPIcs.ESA.2018.8

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:5009565

@@ label / en / label / en @@
+Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension
@@ Property / author @@
+Philip N. Klein
@@ Property / author: Philip N. Klein / rank @@
+Normal rank
@@ Property / describes a project that uses @@
+DIMACS
@@ Property / describes a project that uses: DIMACS / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+VC-Dimension and Shortest Path Algorithms
@@ Property / cites work: VC-Dimension and Shortest Path Algorithms / rank @@
+Normal rank
@@ Property / cites work @@
+Highway Dimension and Provably Efficient Shortest Path Algorithms
+Normal rank
@@ Property / cites work @@
+Q5417667
@@ Property / cites work: Q5417667 / rank @@
+Normal rank
@@ Property / cites work @@
+PTAS FOR k-TOUR COVER PROBLEM ON THE PLANE FOR MODERATELY LARGE VALUES OF k
+Normal rank
@@ Property / cites work @@
+Q4542527
@@ Property / cites work: Q4542527 / rank @@
+Normal rank
@@ Property / cites work @@
+Local Search Heuristics for <i>k</i>-Median and Facility Location Problems
+Normal rank
@@ Property / cites work @@
+A new approximation algorithm for the capacitated vehicle routing problem on a tree
+Normal rank
@@ Property / cites work @@
+Q4526992
@@ Property / cites work: Q4526992 / rank @@
+Normal rank
@@ Property / cites work @@
+Approximate clustering via core-sets
@@ Property / cites work: Approximate clustering via core-sets / rank @@
+Normal rank
@@ Property / cites work @@
+Q3574266
@@ Property / cites work: Q3574266 / rank @@
+Normal rank
@@ Property / cites work @@
+A Quasi-Polynomial-Time Approximation Scheme for Vehicle Routing on Planar and Bounded-Genus Graphs
+Normal rank
@@ Property / cites work @@
+An Improved Approximation for             <i>k</i>             -Median and Positive Correlation in Budgeted Optimization
+Normal rank
@@ Property / cites work @@
+Local Search Yields Approximation Schemes for $k$-Means and $k$-Median in Euclidean and Minor-Free Metrics
+Normal rank
@@ Property / cites work @@
+A quasipolynomial time approximation scheme for Euclidean capacitated vehicle routing
+Normal rank
@@ Property / cites work @@
+Fixed Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs
+Normal rank
@@ Property / cites work @@
+A $$(1+{\varepsilon })$$ ( 1 + ε ) -Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
+Normal rank
@@ Property / cites work @@
+Capacitated arc routing problems
@@ Property / cites work: Capacitated arc routing problems / rank @@
+Normal rank
@@ Property / cites work @@
+Clustering to minimize the maximum intercluster distance
+Normal rank
@@ Property / cites work @@
+Greedy Strikes Back: Improved Facility Location Algorithms
+Normal rank
@@ Property / cites work @@
+Q4471341
@@ Property / cites work: Q4471341 / rank @@
+Normal rank
@@ Property / cites work @@
+Bounds and Heuristics for Capacitated Routing Problems
+Normal rank
@@ Property / cites work @@
+Q4249536
@@ Property / cites work: Q4249536 / rank @@
+Normal rank
@@ Property / cites work @@
+A Best Possible Heuristic for the <i>k</i>-Center Problem
+Normal rank
@@ Property / OpenAlex ID @@
+W2889438244
@@ Property / OpenAlex ID: W2889438244 / rank @@
+Normal rank
@@ Property / title @@
+Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension (English)
+Normal rank