An approximation algorithm for the uniform capacitated \(k\)-means problem

DOI10.1007/s10878-020-00550-yzbMath1502.90146MaRDI QIDQ2082194

Dongmei Zhang, Lu Han, Dong-lei Du, Da-Chuan Xu

Publication date: 4 October 2022

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-020-00550-y

zbMATH Keywords

approximation algorithm; local search; \(k\)-means; uniform capacitated

Mathematics Subject Classification ID

90C59: Approximation methods and heuristics in mathematical programming

90C27: Combinatorial optimization

Uses Software

• apcluster
• APCluster

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Clustering by Passing Messages Between Data Points
• A 3-approximation algorithm for the facility location problem with uniform capacities
• An approximation algorithm for the risk-adjusted two-stage stochastic facility location problem with penalties
• 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
• Clustering large graphs via the singular value decomposition
• An approximation algorithm for the stochastic fault-tolerant facility location problem
• Solving capacitated clustering problems
• NP-hardness of Euclidean sum-of-squares clustering
• Faster algorithms for the constrained \(k\)-means problem
• Improved approximation algorithms for capacitated facility location problems
• An Approximation Algorithm for Uniform Capacitated k-Median Problem with $$1+\epsilon $$ Capacity Violation
• A PTAS for k-means clustering based on weak coresets
• Adaptive Sampling for k-Means Clustering
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Analysis of a Local Search Heuristic for Facility Location Problems
• Least squares quantization in PCM
• Capacitated clustering problems by hybrid simulated annealing and tabu search
• Better Guarantees for $k$-Means and Euclidean $k$-Median by Primal-Dual Algorithms
• On Uniform Capacitated k-Median Beyond the Natural LP Relaxation
• Bi-Factor Approximation Algorithms for Hard Capacitated k-Median Problems
• A Unified Framework for Clustering Constrained Data without Locality Property
• The effectiveness of lloyd-type methods for the k-means problem
• A Multiexchange Local Search Algorithm for the Capacitated Facility Location Problem