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

DOI10.1137/17M1127181zbMath1422.68296arXiv1603.08976MaRDI QIDQ4634026

Mohsen Rezapour, Zachary Friggstad, Mohammad R. 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

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

Related Items (24)

A refined approximation for Euclidean \(k\)-means ⋮ Pattern matching in doubling spaces ⋮ The Ratio-Cut Polytope and K-Means Clustering ⋮ An improved approximation algorithm for squared metric \(k\)-facility location ⋮ 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 ⋮ Better Guarantees for $k$-Means and Euclidean $k$-Median by Primal-Dual Algorithms ⋮ Unnamed Item ⋮ Constructing planar support for non-piercing regions ⋮ A constant FPT approximation algorithm for hard-capacitated \(k\)-means ⋮ Polynomial time approximation schemes for clustering in low highway dimension graphs ⋮ 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 ⋮ Improved Approximation Algorithm for Set Multicover with Non-Piercing Regions. ⋮ Noisy, Greedy and Not so Greedy k-Means++ ⋮ Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering ⋮ FPT Approximation for Constrained Metric k-Median/Means ⋮ Lossy kernelization of same-size clustering ⋮ Improved approximation for prize-collecting red-blue median ⋮ Local search strikes again: PTAS for variants of geometric covering and packing ⋮ 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
• \(k\)-means requires exponentially many iterations even in the plane
• A local search approximation algorithm for \(k\)-means clustering
• Clustering large graphs via the singular value decomposition
• NP-hardness of Euclidean sum-of-squares clustering
• On approximate geometric \(k\)-clustering
• How fast is the \(k\)-means method?
• A 1.488 approximation algorithm for the uncapacitated facility location problem
• A Dependent LP-Rounding Approach for the k-Median Problem
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Polynomial-time approximation schemes for geometric min-sum median clustering
• 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
• Approximate clustering via core-sets
• Bypassing the embedding
• 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
• Local Search Yields a PTAS for $k$-Means in Doubling Metrics
• Local Search Heuristics for k-Median and Facility Location Problems
• Least squares quantization in PCM
• An Improved Approximation for k -Median and Positive Correlation in Budgeted Optimization
• Local search heuristic for k-median and facility location problems
• Smaller coresets for k-median and k-means clustering
• k-means requires exponentially many iterations even in the plane
• Smoothed Analysis of the k-Means Method
• The effectiveness of lloyd-type methods for the k-means problem
• Approximating k-median via pseudo-approximation
• Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering
• A tight bound on approximating arbitrary metrics by tree metrics

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