Local Search Yields Approximation Schemes for $k$-Means and $k$-Median in Euclidean and Minor-Free Metrics

DOI10.1137/17M112717XzbMath1421.68205arXiv1603.09535OpenAlexW2943587448MaRDI QIDQ4634032

Claire Mathieu, Vincent Cohen-Addad, Philip N. Klein

Publication date: 7 May 2019

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1603.09535

zbMATH Keywords

approximation schemesfacility locationplanar graph\(k\)-meansEuclidean metric\(k\)-medianminor-free graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation methods and heuristics in mathematical programming (90C59) Discrete location and assignment (90B80) Approximation algorithms (68W25)

Related Items

A refined approximation for Euclidean \(k\)-means ⋮ An improved approximation algorithm for capacitated correlation clustering problem ⋮ An improved approximation algorithm for squared metric \(k\)-facility location ⋮ Unnamed Item ⋮ An improved \((1+1)\) evolutionary algorithm for \(k\)-Median clustering problem with performance guarantee ⋮ An exact algorithm for stable instances of the \(k\)-means problem with penalties in fixed-dimensional Euclidean space ⋮ On the geometric set multicover problem ⋮ Better guarantees for \(k\)-median with service installation costs ⋮ Improved PTAS for the constrained \(k\)-means problem ⋮ Unnamed Item ⋮ Secure delegated quantum algorithms for solving Mahalanobis distance ⋮ Constructing planar support for non-piercing regions ⋮ Quantum algorithms for similarity measurement based on Euclidean distance ⋮ A constant FPT approximation algorithm for hard-capacitated \(k\)-means ⋮ A Streaming Algorithm for k-Means with Approximate Coreset ⋮ Polynomial time approximation schemes for clustering in low highway dimension graphs ⋮ Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering ⋮ Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension ⋮ Lossy kernelization of same-size clustering ⋮ Local search strikes again: PTAS for variants of geometric covering and packing ⋮ The seeding algorithm for spherical \(k\)-means clustering with penalties ⋮ Stability and Recovery for Independence Systems ⋮ Lossy kernelization of same-size clustering

Uses Software

• k-means++

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation algorithms for maximum independent set of pseudo-disks
• A local search approximation algorithm for \(k\)-means clustering
• Smaller coresets for \(k\)-median and \(k\)-means clustering
• A 1.488 approximation algorithm for the uncapacitated facility location problem
• Approximating $k$-Median via Pseudo-Approximation
• Are Stable Instances Easy?
• Improved Spectral-Norm Bounds for Clustering
• A Nearly Linear-Time Approximation Scheme for the Euclidean k-Median Problem
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Worst-Case and Smoothed Analysis of the ICP Algorithm, with an Application to the k-Means Method
• Linear-time approximation schemes for clustering problems in any dimensions
• A new greedy approach for facility location problems
• Approximate clustering via core-sets
• On coresets for k-means and k-median clustering
• A PTAS for k-means clustering based on weak coresets
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• Heuristics for the fixed cost median problem
• Greedy Strikes Back: Improved Facility Location Algorithms
• Approximation algorithms for NP-complete problems on planar graphs
• Analysis of a Local Search Heuristic for Facility Location Problems
• Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
• Local Search Yields a PTAS for $k$-Means in Doubling Metrics
• Approximate Clustering via Metric Partitioning
• Local Search Heuristics for k-Median and Facility Location Problems
• Improved Combinatorial Algorithms for Facility Location Problems
• An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization
• Smoothed Analysis of the k-Means Method
• The effectiveness of lloyd-type methods for the k-means problem
• A unified framework for approximating and clustering data
• Clustering under Perturbation Resilience