Better Guarantees for $k$-Means and Euclidean $k$-Median by Primal-Dual Algorithms

DOI10.1137/18M1171321zbMath1450.90005arXiv1612.07925MaRDI QIDQ5117377

Justin Ward, Ashkan Norouzi-Fard, Ola Svensson, Sara Ahmadian

Publication date: 25 August 2020

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

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

zbMATH Keywords

clusteringapproximation algorithm\(k\)-meansprimal-dual\(k\)-medianLP-based algorithm

Mathematics Subject Classification ID

Linear programming (90C05) Approximation methods and heuristics in mathematical programming (90C59) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Discrete approximations in optimal control (49M25)

Related Items (43)

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 ⋮ Approximation algorithms for two variants of correlation clustering problem ⋮ 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 clustering with discounts ⋮ Better guarantees for \(k\)-median with service installation costs ⋮ Discrete facility location in machine learning ⋮ Local search approximation algorithms for the \(k\)-means problem with penalties ⋮ Improved PTAS for the constrained \(k\)-means problem ⋮ Polynomial approximate discretization of geometric centers in high-dimensional Euclidean space ⋮ Unnamed Item ⋮ Secure delegated quantum algorithms for solving Mahalanobis distance ⋮ Approximation algorithms for fair \(k\)-median problem without fairness violation ⋮ Unnamed Item ⋮ Quantum algorithms for similarity measurement based on Euclidean distance ⋮ A constant FPT approximation algorithm for hard-capacitated \(k\)-means ⋮ Polynomial time approximation schemes for clustering in low highway dimension graphs ⋮ Noisy, Greedy and Not so Greedy k-Means++ ⋮ The Parallel Seeding Algorithm for k-Means Problem with Penalties ⋮ Approximation algorithms for fuzzy \(C\)-means problem based on seeding method ⋮ A unified framework of FPT approximation algorithms for clustering problems ⋮ Lossy kernelization of same-size clustering ⋮ Approximating the \(\tau\)-relaxed soft capacitated facility location problem ⋮ New algorithms for a simple measure of network partitioning ⋮ Approximation algorithm for the balanced 2-correlation clustering problem on well-proportional graphs ⋮ The spherical \(k\)-means++ algorithm via local search ⋮ Local search algorithm for the spherical \(k\)-means problem with outliers ⋮ The seeding algorithm for \(k\)-means problem with penalties ⋮ Simpler and Better Algorithms for Minimum-Norm Load Balancing ⋮ A Lottery Model for Center-Type Problems With Outliers ⋮ The seeding algorithms for spherical \(k\)-means clustering ⋮ On perturbation resilience of non-uniform \(k\)-center ⋮ The approximation algorithm based on seeding method for functional \(k\)-means problem ⋮ The bi-criteria seeding algorithms for two variants of \(k\)-means problem ⋮ An approximation algorithm for the uniform capacitated \(k\)-means problem ⋮ The seeding algorithm for spherical \(k\)-means clustering with penalties ⋮ Approximation algorithm for spherical \(k\)-means problem with penalty ⋮ Lossy kernelization of same-size clustering ⋮ Improved approximation algorithms for solving the squared metric \(k\)-facility location problem ⋮ On parameterized approximation algorithms for balanced clustering

Uses Software

• k-means++

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved and simplified inapproximability for \(k\)-means
• \(k\)-means requires exponentially many iterations even in the plane
• A local search approximation algorithm for \(k\)-means clustering
• Approximation algorithms for geometric median problems
• On approximate geometric \(k\)-clustering
• A 1.488 approximation algorithm for the uncapacitated facility location problem
• Approximating $k$-Median via Pseudo-Approximation
• The Design of Approximation Algorithms
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• A new greedy approach for facility location problems
• A PTAS for k-means clustering based on weak coresets
• Improved Approximation Algorithms for the Uncapacitated Facility Location Problem
• 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
• Improved Combinatorial Algorithms for Facility Location Problems
• An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization
• The effectiveness of lloyd-type methods for the k-means problem
• An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem
• Algorithms - ESA 2003

This page was built for publication: Better Guarantees for $k$-Means and Euclidean $k$-Median by Primal-Dual Algorithms