Polynomial time approximation schemes for clustering in low highway dimension graphs

DOI10.1016/J.JCSS.2021.06.002MaRDI QIDQ2229951zbMATH OpenOpenAlexFDO

Authors Andreas Emil Feldmann, David Saulpic

Publication date 17 September 2021

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2006.12897, https://drops.dagstuhl.de/opus/volltexte/2020/12912/

zbMATH Keywords

clusteringapproximation algorithmhighway dimension

Mathematics Subject Classification ID

Computer science (68-XX)

Recommendations

• Polynomial time approximation schemes for clustering in low highway dimension graphs
• Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension
• Fixed-parameter approximations for \(k\)-center problems in low highway dimension graphs
• Fixed parameter approximations for \(k\)-center problems in low highway dimension graphs
• Travelling on graphs with small highway dimension

Cites work

• scientific article; zbMATH DE number 1775394 (Why is no real title available?)
• scientific article; zbMATH DE number 7651185 (Why is no real title available?)
• A 1.488 approximation algorithm for the uncapacitated facility location problem
• A Nearly Linear-Time Approximation Scheme for the Euclidean k-Median Problem
• A new greedy approach for facility location problems
• An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization
• Better guarantees for \(k\)-means and Euclidean \(k\)-median by primal-dual algorithms
• Bypassing the embedding
• Fixed-parameter approximations for \(k\)-center problems in low highway dimension graphs
• Greedy Strikes Back: Improved Facility Location Algorithms
• Hierarchy of Transportation Network Parameters and Hardness Results
• Highway dimension and provably efficient shortest path algorithms
• Highway dimension, shortest paths, and provably efficient algorithms
• Local Search Yields Approximation Schemes for $k$-Means and $k$-Median in Euclidean and Minor-Free Metrics
• Local search yields a PTAS for \(k\)-means in doubling metrics
• Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension
• The hardness of approximation of Euclidean \(k\)-means
• Travelling on graphs with small highway dimension
• VC-dimension and shortest path algorithms

Cited in

(1)

• Generalized \(k\)-center: distinguishing doubling and highway dimension

This page was built for publication: Polynomial time approximation schemes for clustering in low highway dimension graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2229951)