An approximation algorithm for the uniform capacitated k-means problem

Lu Han (), Dachuan Xu (), Donglei Du () and Dongmei Zhang ()
Additional contact information
Lu Han: Beijing University of Technology
Dachuan Xu: Beijing University of Technology
Donglei Du: University of New Brunswick
Dongmei Zhang: Shandong Jianzhu University

Journal of Combinatorial Optimization, No 0, 12 pages

Abstract: Abstract In this paper, we consider the uniform capacitated k-means problem (UC-k-means), an extension of the classical k-means problem (k-means) in machine learning. In the UC-k-means, we are given a set $$\mathcal {D}$$D of n points in d-dimensional space and an integer k. Every point in the d-dimensional space has an uniform capacity which is an upper bound on the number of points in $$\mathcal {D}$$D that can be connected to this point. Every two-point pair in the space has an associated connecting cost, which is equal to the square of the distance between these two points. We want to find at most k points in the space as centers and connect every point in $$\mathcal {D}$$D to some center without violating the capacity constraint, such that the total connecting costs is minimized. Based on the technique of local search, we present a bi-criteria approximation algorithm, which has a constant approximation guarantee and violates the cardinality constraint within a constant factor, for the UC-k-means.

Keywords: k-means; Uniform capacitated; Approximation algorithm; Local search (search for similar items in EconPapers)
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-020-00550-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v::y::i::d:10.1007_s10878-020-00550-y

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-020-00550-y

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().