A Nearly Linear-Time Approximation Scheme for the Euclidean k-Median Problem
From MaRDI portal
Publication:3507519
DOI10.1137/S0097539702404055zbMath1144.68052MaRDI QIDQ3507519
No author found.
Publication date: 19 June 2008
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Euclidean spaceapproximation schemesfacility locationapproximation algorithmslinear time\(k\)-median
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Discrete location and assignment (90B80) Approximation algorithms (68W25) Randomized algorithms (68W20)
Related Items (24)
Clustering through continuous facility location problems ⋮ A PTAS for the geometric connected facility location problem ⋮ On some variants of Euclidean \(k\)-supplier ⋮ \(k\)-median: exact recovery in the extended stochastic ball model ⋮ Universal Algorithms for Clustering Problems ⋮ The Euclidean k-Supplier Problem ⋮ Some results on approximate 1-median selection in metric spaces ⋮ A Modern View on Stability of Approximation ⋮ Unnamed Item ⋮ \(\mathrm{M}^p\)UFLP: universal facility location problem in the \(p\)-th power of metric space ⋮ Approximation algorithms for fair \(k\)-median problem without fairness violation ⋮ Parameterized \(k\)-clustering: tractability island ⋮ Polynomial time approximation schemes for clustering in low highway dimension graphs ⋮ Local Search Yields Approximation Schemes for $k$-Means and $k$-Median in Euclidean and Minor-Free Metrics ⋮ A quasipolynomial time approximation scheme for Euclidean capacitated vehicle routing ⋮ An approximation algorithm for the Euclidean incremental median problem ⋮ Local search algorithms for the red-blue median problem ⋮ Approximating \(k\)-hop minimum spanning trees in Euclidean metrics ⋮ Faster balanced clusterings in high dimension ⋮ Kinetic facility location ⋮ Unnamed Item ⋮ A unified framework for clustering constrained data without locality property ⋮ The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme ⋮ Probabilistic \(k\)-median clustering in data streams
This page was built for publication: A Nearly Linear-Time Approximation Scheme for the Euclidean k-Median Problem
