Top

Optimization and Engineering

Published in:

30-04-2020 | Research Article

A constant FPT approximation algorithm for hard-capacitated k-means

Authors: Yicheng Xu, Rolf H. Möhring, Dachuan Xu, Yong Zhang, Yifei Zou

Published in: Optimization and Engineering | Issue 3/2020

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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.

previous article Announcement: Howard Rosenbrock Prize 2019

next article A generalized methodology for multidisciplinary design optimization using surrogate modelling and multifidelity analysis

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Adamczyk M, Byrka J, Marcinkowski J, Meesum S M, Wlodarczyk M (2019) Constant-factor FPT approximation for capacitated \(k\)-median. In: Proceedings of the 27th annual European symposium on algorithms, pp 1:1–1:14

Ahmadian S, Norouzi-Fard A, Svensson O, Ward J (2019) Better guarantees for \(k\)-means and Euclidean \(k\)-median by primal-dual algorithms. SIAM J Comput. https://doi.org/10.1137/18m1171321 CrossRef

Aloise D, Deshpande A, Hansen P, Popat P (2009) NP-hardness of Euclidean sum-of-squares clustering. Mach Learn 75:245–249CrossRef

Arthur D, Vassilvitskii S (2007) \(K\)-means++: the advantages of careful seeding. In: Proceedings of the 8th annual ACM-SIAM symposium on discrete algorithms, pp 1027–1035

Awasthi P, Charikar M, Krishnaswamy R, Sinop AK (2015) The hardness of approximation of Euclidean \(k\)-means. In: Proceedings of the 31st international symposium on computational geometry, pp 754–767

Bahmani B, Moseley B, Vattani A, Kumar R, Vassilvitskii S (2012) Scalable \(k\)-means++. In: Proceedings of the 38th international conference on very large data bases, pp 622–633

Bandyapadhyay S, Varadarajan K (2016) On variants of \(k\)-means clustering. In: Proceedings of the 32nd international symposium on computational geometry, pp 14:1–14:15

Berkhin P (2006) A survey of clustering data mining techniques. In: Kogan J, Nicholas C, Teboulle M (eds) Grouping multidimensional data. Springer, Berlin

Byrka J, Rybicki B, Uniyal S (2016) An approximation algorithm for uniform capacitated \(k\)-median problem with \(1+\epsilon\) capacity iolation. In: Proceedings of the 18th international conference on integer programming and combinatorial optimization, pp 262–274

Cohen-Addad V (2020) Approximation schemes for capacitated clustering in doubling metrics. In: Proceedings of the 14th annual ACM-SIAM symposium on discrete algorithms, pp 2241–2259

Cohen-Addad V, Li J (2019) On the fixed-parameter tractability of capacitated clustering. In: Proceedings of the 46th international colloquium on automata, languages, and programming, pp 41:1–41:14

Cohen-Addad V, Klein PN, Mathieu C (2019) Local search yields approximation schemes for \(k\)-means and \(k\)-median in Euclidean and minor-free metrics. SIAM J Comput 48(2):644–667MathSciNetCrossRef

Friggstad Z, Rezapour M, Salavatipour MR (2019) Local search yields a PTAS for \(k\)-means in doubling metrics. SIAM J Comput 48(2):452–480MathSciNetCrossRef

Hsu D, Telgarsky M (2016) Greedy bi-criteria approximations for \(k\)-medians and \(k\)-means. arXiv preprint arXiv:1607.06203

Kanungo T, Mount DM, Netanyahu NS, Piatko CD, Silverman R, Wu AY (2004) A local search approximation algorithm for \(k\)-means clustering. Comput Geom 28:89–112MathSciNetCrossRef

Lee E, Schmidt M, Wright J (2016) Improved and simplified inapproximability for \(k\)-means. Inf Process Lett 120:40–43MathSciNetCrossRef

Lloyd S (1982) Least squares quantization in PCM. IEEE Trans Inf Theory 28(2):129–137MathSciNetCrossRef

Li S (2013) A 1.488 approximation algorithm for the uncapacitated facility location problem. Inf Comput 222:45–58MathSciNetCrossRef

Li S (2017) On uniform capacitated \(k\)-median beyond the natural LP relaxation. ACM Trans Algorithms 13(2):Article 22

Schrijver A (2003) Combinatorial optimization: polyhedra and efficiency. Springer, BerlinMATH

Xu Y, Möhring R H, Xu D, Zhang Y, and Zou Y (2019) A constant parameterized approximation for hard capacitated \(k\)-means. arXiv:1901.04628

Zhang J, Chen B, Ye Y (2005) A multiexchange local search algorithm for the capacitated facility location problem. Math Oper Res 30(2):389–403MathSciNetCrossRef

Title: A constant FPT approximation algorithm for hard-capacitated k-means
Authors: Yicheng Xu
Rolf H. Möhring
Dachuan Xu
Yong Zhang
Yifei Zou
Publication date: 30-04-2020
Publisher: Springer US
Published in: Optimization and Engineering / Issue 3/2020
Print ISSN: 1389-4420
Electronic ISSN: 1573-2924
DOI: https://doi.org/10.1007/s11081-020-09503-0

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Other articles of this Issue 3/2020

A simulation–optimization framework for short-term underground mine production scheduling

A solution method for heterogeneity involving present bias

Announcement: Howard Rosenbrock Prize 2019

Deterministic global optimization of steam cycles using the IAPWS-IF97 model

A generalized methodology for multidisciplinary design optimization using surrogate modelling and multifidelity analysis

Robust principal component analysis using facial reduction

Premium Partners