Local Search Yields a PTAS for k-Means in Doubling Metrics

DOI10.1137/17M1127181zbMATH Open1422.68296arXiv1603.08976MaRDI QIDQ4634026FDOQ4634026

Mohsen Rezapour, Zachary Friggstad, Mohammad Salavatipour

Publication date: 7 May 2019

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

Abstract: The most well known and ubiquitous clustering problem encountered in nearly every branch of science is undoubtedly $k$-means: given a set of data points and a parameter $k$, select $k$ centres and partition the data points into $k$ clusters around these centres so that the sum of squares of distances of the points to their cluster centre is minimized. Typically these data points lie $mathbb{R}^d$ for some $dgeq2$. $k$-means and the first algorithms for it were introduced in the 1950's. Since then, hundreds of papers have studied this problem and many algorithms have been proposed for it. The most commonly used algorithm is known as Lloyd-Forgy, which is also referred to as "the" $k$-means algorithm, and various extensions of it often work very well in practice. However, they may produce solutions whose cost is arbitrarily large compared to the optimum solution. Kanungo et al. [2004] analyzed a simple local search heuristic to get a polynomial-time algorithm with approximation ratio $9+epsilon$ for any fixed $epsilon>0$ for $k$-means in Euclidean space. Finding an algorithm with a better approximation guarantee has remained one of the biggest open questions in this area, in particular whether one can get a true PTAS for fixed dimension Euclidean space. We settle this problem by showing that a simple local search algorithm provides a PTAS for $k$-means in $mathbb{R}^d$ for any fixed $d$. More precisely, for any error parameter $epsilon>0$, the local search algorithm that considers swaps of up to $ho=d^{O(d)}cdot{epsilon}^{-O(d/epsilon)}$ centres at a time finds a solution using exactly $k$ centres whose cost is at most a $(1+epsilon)$-factor greater than the optimum. Finally, we provide the first demonstration that local search yields a PTAS for the uncapacitated facility location problem and $k$-median with non-uniform opening costs in doubling metrics.

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

zbMATH Keywords

\(k\)-meanspolynomial time approximation schemedoubling metrics

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Cites Work

• Title not available (Why is that?)
• Least squares quantization in PCM
• NP-hardness of Euclidean sum-of-squares clustering
• The effectiveness of lloyd-type methods for the k-means problem
• Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering
• Approximating k-median via pseudo-approximation
• A 1.488 approximation algorithm for the uncapacitated facility location problem
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Clustering large graphs via the singular value decomposition
• Title not available (Why is that?)
• k-means requires exponentially many iterations even in the plane
• \(k\)-means requires exponentially many iterations even in the plane
• A Dependent LP-Rounding Approach for the k-Median Problem
• Title not available (Why is that?)
• Local search heuristic for k-median and facility location problems
• A tight bound on approximating arbitrary metrics by tree metrics
• Local Search Heuristics for k-Median and Facility Location Problems
• On Coresets for k-Median and k-Means Clustering in Metric and Euclidean Spaces and Their Applications
• Linear-time approximation schemes for clustering problems in any dimensions
• On approximate geometric \(k\)-clustering
• Approximate clustering via core-sets
• On coresets for k-means and k-median clustering
• Approximation schemes for clustering problems
• A PTAS for k-means clustering based on weak coresets
• The Planar k-Means Problem is NP-Hard
• Title not available (Why is that?)
• Smaller coresets for k-median and k-means clustering
• Smoothed Analysis of the k-Means Method
• A local search approximation algorithm for \(k\)-means clustering
• Bypassing the embedding
• How fast is the \(k\)-means method?
• Polynomial-time approximation schemes for geometric min-sum median clustering
• Local Search Yields a PTAS for $k$-Means in Doubling Metrics
• Title not available (Why is that?)
• An Improved Approximation for k -Median and Positive Correlation in Budgeted Optimization
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (27)

• A constant FPT approximation algorithm for hard-capacitated \(k\)-means
• Pattern matching in doubling spaces
• Near-linear Time Approximation Schemes for Clustering in Doubling Metrics
• Title not available (Why is that?)
• 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
• A refined approximation for Euclidean \(k\)-means
• Improved Approximation Algorithm for Set Multicover with Non-Piercing Regions.
• Local Search Yields Approximation Schemes for $k$-Means and $k$-Median in Euclidean and Minor-Free Metrics
• FPT Approximation for Constrained Metric k-Median/Means
• An improved approximation algorithm for squared metric \(k\)-facility location
• Local search strikes again: PTAS for variants of geometric covering and packing
• Improved approximation for prize-collecting red-blue median
• Better Guarantees for $k$-Means and Euclidean $k$-Median by Primal-Dual Algorithms
• An exact algorithm for stable instances of the \(k\)-means problem with penalties in fixed-dimensional Euclidean space
• On the geometric set multicover problem
• Noisy, Greedy and Not so Greedy k-Means++
• Constructing planar support for non-piercing regions
• Approximation algorithms for robust clustering problems using local search techniques
• Title not available (Why is that?)
• The Ratio-Cut Polytope and K-Means Clustering
• Improved PTAS for the constrained \(k\)-means problem
• FPT approximation for capacitated clustering with outliers
• Local Search Yields a PTAS for $k$-Means in Doubling Metrics
• Better guarantees for \(k\)-median with service installation costs
• Lossy kernelization of same-size clustering
• Lossy kernelization of same-size clustering

Uses Software

• k-means++

This page was built for publication: Local Search Yields a PTAS for $k$-Means in Doubling Metrics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4634026)