Local search yields a PTAS for k-means in doubling metrics

DOI10.1137/17M1127181MaRDI QIDQ4634026zbMATH OpenFDO

Authors Zachary Friggstad, Mohsen Rezapour, Mohammad Salavatipour

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.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)

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.

Recommendations

• On variants of \(k\)-means clustering
• Local Search Yields Approximation Schemes for $k$-Means and $k$-Median in Euclidean and Minor-Free Metrics
• A local search approximation algorithm for \(k\)-means clustering
• A local search approximation algorithm for \(k\)-means clustering
• Near-linear Time Approximation Schemes for Clustering in Doubling Metrics

Cites work

• scientific article; zbMATH DE number 6381735 (Why is no real title available?)
• scientific article; zbMATH DE number 5506203 (Why is no real title available?)
• scientific article; zbMATH DE number 1775394 (Why is no real title available?)
• A 1.488 approximation algorithm for the uncapacitated facility location problem
• A PTAS for k-means clustering based on weak coresets
• A dependent LP-rounding approach for the \(k\)-median problem
• A local search approximation algorithm for \(k\)-means clustering
• A tight bound on approximating arbitrary metrics by tree metrics
• An Improved Approximation for k -Median and Positive Correlation in Budgeted Optimization
• Approximate clustering via core-sets
• Approximating k-median via pseudo-approximation
• Approximation schemes for clustering problems
• Bypassing the embedding
• Clustering large graphs via the singular value decomposition
• Effectiveness of local search for geometric optimization
• How fast is the \(k\)-means method?
• Least squares quantization in PCM
• Linear-time approximation schemes for clustering problems in any dimensions
• Local Search Heuristics for k-Median and Facility Location Problems
• Local search heuristic for k-median and facility location problems
• Local search yields a PTAS for \(k\)-means in doubling metrics
• NP-hardness of Euclidean sum-of-squares clustering
• On Coresets for k-Median and k-Means Clustering in Metric and Euclidean Spaces and Their Applications
• On approximate geometric \(k\)-clustering
• On coresets for k-means and k-median clustering
• On variants of \(k\)-means clustering
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Polynomial-time approximation schemes for geometric min-sum median clustering
• Smaller coresets for \(k\)-median and \(k\)-means clustering
• Smoothed analysis of the \(k\)-means method
• The Planar k-Means Problem is NP-Hard
• The effectiveness of Lloyd-type methods for the \(k\)-means problem
• The hardness of approximation of Euclidean \(k\)-means
• Turning big data into tiny data: constant-size coresets for \(k\)-means, PCA and projective clustering
• Universal \({\epsilon}\)-approximators for integrals
• \(k\)-means requires exponentially many iterations even in the plane
• \(k\)-means requires exponentially many iterations even in the plane

Cited in

(32)

• Lossy kernelization of same-size clustering
• 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
• The ratio-cut polytope and K-means clustering
• scientific article; zbMATH DE number 7378687 (Why is no real title available?)
• A fast approximation scheme for low-dimensional \(k\)-means
• 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.
• Approximation schemes for clustering with outliers
• Approximation schemes for clustering with outliers
• 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
• On variants of \(k\)-means clustering
• An improved approximation algorithm for squared metric \(k\)-facility location
• FPT Approximation for Constrained Metric k-Median/Means
• Improved approximation for prize-collecting red-blue median
• Local search strikes again: PTAS for variants of geometric covering and packing
• An exact algorithm for stable instances of the k-means problem with penalties in fixed-dimensional Euclidean space
• On the geometric set multicover problem
• Constructing planar support for non-piercing regions
• Noisy, Greedy and Not so Greedy k-Means++
• Approximation algorithms for robust clustering problems using local search techniques
• Improved PTAS for the constrained \(k\)-means problem
• scientific article; zbMATH DE number 7651185 (Why is no real title available?)
• A local search approximation algorithm for \(k\)-means clustering
• FPT approximation for capacitated clustering with outliers
• Better guarantees for \(k\)-means and Euclidean \(k\)-median by primal-dual algorithms
• Better guarantees for \(k\)-median with service installation costs
• Lossy kernelization of same-size clustering

Describes a project that uses

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)