An approximation algorithm for the uniform capacitated \(k\)-means problem
From MaRDI portal
Publication:2082194
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
90C59: Approximation methods and heuristics in mathematical programming
90C27: Combinatorial optimization
Uses Software
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