Improved PTAS for the constrained k-means problem

Qilong Feng, Jiaxin Hu, Neng Huang and Jianxin Wang ()
Additional contact information
Qilong Feng: Central South University
Jiaxin Hu: Central South University
Neng Huang: Central South University
Jianxin Wang: Central South University

Journal of Combinatorial Optimization, 2019, vol. 37, issue 4, No 1, 1110 pages

Abstract: Abstract The k-means problem has been paid lots of attention in many fields, and each cluster of the k-means problem always satisfies locality property. In this paper, we study the constrained k-means problem, where the clusters do not satisfy locality property and can be an arbitrary partition of the set of points. Ding and Xu presented a unified framework with running time $$O(2^{poly (k/\epsilon )} (\log n)^{k+1} nd)$$ O ( 2 p o l y ( k / ϵ ) ( log n ) k + 1 n d ) by applying uniform sampling and simplex lemma techniques such that a collection of size $$O(2^{poly (k/\epsilon )} (\log n)^{k+1})$$ O ( 2 p o l y ( k / ϵ ) ( log n ) k + 1 ) of candidate sets containing approximate centers is obtained. Then, the collection is enumerated to get the one that can induce a $$(1+\epsilon )$$ ( 1 + ϵ ) -approximation solution for the constrained k-means problem. By applying $$D^2$$ D 2 -sampling technique, Bhattacharya, Jaiswal, and Kumar presented an algorithm with running time $$O(2^{{\tilde{O}}(k/\epsilon )}nd)$$ O ( 2 O ~ ( k / ϵ ) n d ) , which is bounded by $$O(2^k( \frac{2123ek}{\epsilon ^3})^{64k/\epsilon }knd)$$ O ( 2 k ( 2123 e k ϵ 3 ) 64 k / ϵ k n d ) . The algorithm outputs a collection of size $$O(2^k( \frac{2123ek}{\epsilon ^3})^{64k/\epsilon })$$ O ( 2 k ( 2123 e k ϵ 3 ) 64 k / ϵ ) of candidate sets containing approximate centers. In this paper, we present an algorithm with running time $$O((\frac{1891ek}{\epsilon ^2})^{8k/\epsilon }nd)$$ O ( ( 1891 e k ϵ 2 ) 8 k / ϵ n d ) such that a collection of size $$O((\frac{1891ek}{\epsilon ^2})^{8k/\epsilon }n)$$ O ( ( 1891 e k ϵ 2 ) 8 k / ϵ n ) of candidate sets containing approximate centers can be obtained.

Keywords: k-means; Approximation algorithm; PTAS (search for similar items in EconPapers)
Date: 2019
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-018-0340-4 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:37:y:2019:i:4:d:10.1007_s10878-018-0340-4

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

DOI: 10.1007/s10878-018-0340-4

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 ().