Polynomial time approximation schemes for clustering in low highway dimension graphs
From MaRDI portal
Publication:5874516
DOI10.4230/LIPICS.ESA.2020.46MaRDI QIDQ5874516FDOQ5874516
Authors: Andreas Emil Feldmann, David Saulpic 
Publication date: 7 February 2023
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
- A 1.488 approximation algorithm for the uncapacitated facility location problem
- Title not available (Why is that?)
- Highway dimension, shortest paths, and provably efficient algorithms
- An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization
- A Nearly Linear-Time Approximation Scheme for the Euclidean k-Median Problem
- The hardness of approximation of Euclidean \(k\)-means
- Bypassing the embedding
- Fixed-parameter approximations for \(k\)-center problems in low highway dimension graphs
- Local Search Yields a PTAS for $k$-Means in Doubling Metrics
- Hierarchy of Transportation Network Parameters and Hardness Results
- Better guarantees for \(k\)-means and Euclidean \(k\)-median by primal-dual algorithms
- Local Search Yields Approximation Schemes for $k$-Means and $k$-Median in Euclidean and Minor-Free Metrics
- Travelling on graphs with small highway dimension
Cited In (3)
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 Q5874516)
