Polynomial time approximation schemes for clustering in low highway dimension graphs
From MaRDI portal
Publication:2229951
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
Related Items (1)
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
