Polynomial time approximation schemes for clustering in low highway dimension graphs

DOI10.1016/j.jcss.2021.06.002OpenAlexW3185122763MaRDI QIDQ2229951

David Saulpic, Andreas Emil Feldmann

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

zbMATH Keywords

clusteringapproximation algorithmhighway dimension

Mathematics Subject Classification ID

Computer science (68-XX)

Related Items (1)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fixed-parameter approximations for \(k\)-center problems in low highway dimension graphs
• A 1.488 approximation algorithm for the uncapacitated facility location problem
• VC-Dimension and Shortest Path Algorithms
• Highway Dimension and Provably Efficient Shortest Path Algorithms
• A Nearly Linear-Time Approximation Scheme for the Euclidean k-Median Problem
• A new greedy approach for facility location problems
• Bypassing the embedding
• Greedy Strikes Back: Improved Facility Location Algorithms
• Local Search Yields a PTAS for $k$-Means in Doubling Metrics
• Local Search Yields Approximation Schemes for $k$-Means and $k$-Median in Euclidean and Minor-Free Metrics
• Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension
• Better Guarantees for $k$-Means and Euclidean $k$-Median by Primal-Dual Algorithms
• An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization
• Hierarchy of Transportation Network Parameters and Hardness Results
• Travelling on graphs with small highway dimension

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