Indexed by:
Abstract:
Hard-capacitated k-means (HCKM) is one of the fundamental problems remaining open in combinatorial optimization and engineering. In HCKM, one is required to partition a given n-point set into k disjoint clusters with known capacity so as to minimize the sum of within-cluster variances. It is known to be at least APX-hard, and most of the work on it has been done from a meta heuristic or bi-criteria approximation perspective. To the best our knowledge, no constant approximation algorithm or existence proof of such an algorithm is known. As our main contribution, we propose an FPT(k) approximation algorithm with constant performance guarantee for HCKM in this paper.
Keyword:
Reprint Author's Address:
Email:
Source :
OPTIMIZATION AND ENGINEERING
ISSN: 1389-4420
Year: 2020
Issue: 3
Volume: 21
Page: 709-722
2 . 1 0 0
JCR@2022
ESI Discipline: ENGINEERING;
ESI HC Threshold:115
Cited Count:
WoS CC Cited Count: 10
SCOPUS Cited Count: 13
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 9
Affiliated Colleges: