A constant FPT approximation algorithm for hard-capacitated k-means
| Autor: | Yicheng Xu, Yong Zhang, Rolf H. Möhring, Dachuan Xu, Yifei Zou |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
021103 operations research
Control and Optimization Mechanical Engineering 0211 other engineering and technologies k-means clustering Aerospace Engineering Approximation algorithm Piecewise constant approximation 02 engineering and technology Disjoint sets Performance guarantee Combinatorics Combinatorial optimization Meta heuristic Partition (number theory) 021108 energy Electrical and Electronic Engineering Software Civil and Structural Engineering Mathematics |
| Zdroj: | Optimization and Engineering. 21:709-722 |
| ISSN: | 1573-2924 1389-4420 |
| DOI: | 10.1007/s11081-020-09503-0 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink