An approximation algorithm for the uniform capacitated \(k\)-means problem
type: Item
instance of: scholarly article
title: An approximation algorithm for the uniform capacitated \(k\)-means problem
zbMATH Open document ID: 1502.90146
author: Lu Han
author: Dongmei Zhang
author: Dachuan Xu
author: Donglei Du
published in: Journal of Combinatorial Optimization
publication date: 2022-10-04T00:00:00Z
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C59
zbMATH DE Number: 7595919
zbMATH Keywords: \(k\)-means
zbMATH Keywords: uniform capacitated
zbMATH Keywords: approximation algorithm
zbMATH Keywords: local search
describes a project that uses: APCluster
describes a project that uses: apcluster
MaRDI profile type: Publication
full work available at URL: s10878-020-00550-y
OpenAlex ID: W3008182893
cites work: Adaptive Sampling for k-Means Clustering
cites work: A 3-approximation algorithm for the facility location problem with uniform capacities
cites work: Better Guarantees for $k$-Means and Euclidean $k$-Median by Primal-Dual Algorithms
cites work: NP-hardness of Euclidean sum-of-squares clustering
cites work: Q3601533
cites work: Q2934696
cites work: Q5368726
cites work: Faster algorithms for the constrained \(k\)-means problem
cites work: Bi-Factor Approximation Algorithms for Hard Capacitated k-Median Problems
cites work: An Approximation Algorithm for Uniform Capacitated k-Median Problem with $$1+\epsilon $$ Capacity Violation
cites work: Improved approximation algorithms for capacitated facility location problems
cites work: Q4598213
cites work: A Unified Framework for Clustering Constrained Data without Locality Property
cites work: Clustering large graphs via the singular value decomposition
cites work: A PTAS for k-means clustering based on weak coresets
cites work: Clustering by Passing Messages Between Data Points
cites work: Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
cites work: A local search approximation algorithm for \(k\)-means clustering
cites work: Analysis of a Local Search Heuristic for Facility Location Problems
cites work: Improved and simplified inapproximability for \(k\)-means
cites work: On Uniform Capacitated k-Median Beyond the Natural LP Relaxation
cites work: Least squares quantization in PCM
cites work: Solving capacitated clustering problems
cites work: Capacitated clustering problems by hybrid simulated annealing and tabu search
cites work: The effectiveness of lloyd-type methods for the k-means problem
cites work: An approximation algorithm for the risk-adjusted two-stage stochastic facility location problem with penalties
cites work: \(k\)-means requires exponentially many iterations even in the plane
cites work: An approximation algorithm for the stochastic fault-tolerant facility location problem
cites work: A Multiexchange Local Search Algorithm for the Capacitated Facility Location Problem
DOI: 10.1007/S10878-020-00550-Y
description: scientific article; zbMATH DE number 7595919