Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Constant-Factor Approximation Algorithms for Some Maximin Multi-clustering Problems. / Khandeev, Vladimir; Neshchadim, Sergey.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer Science and Business Media Deutschland GmbH, 2023. p. 85-100 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13930 LNCS).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
}
TY - GEN
T1 - Constant-Factor Approximation Algorithms for Some Maximin Multi-clustering Problems
AU - Khandeev, Vladimir
AU - Neshchadim, Sergey
N1 - The study presented was supported by the Russian Academy of Science (the Program of basic research), project FWNF-2022-0015.
PY - 2023
Y1 - 2023
N2 - We consider several problems of searching for a family of non-intersecting subsets in a finite set of points of Euclidean space. In these problems, it is required to maximize the minimum cluster’s cardinality under constraint on each cluster’s scatter. The scatter is the sum of the distances from the cluster elements to the center, which is defined differently in each of the problems. We show that these problems are NP-hard in the case of an arbitrary fixed number of clusters and propose polynomial constant-factor approximation algorithms for this case.
AB - We consider several problems of searching for a family of non-intersecting subsets in a finite set of points of Euclidean space. In these problems, it is required to maximize the minimum cluster’s cardinality under constraint on each cluster’s scatter. The scatter is the sum of the distances from the cluster elements to the center, which is defined differently in each of the problems. We show that these problems are NP-hard in the case of an arbitrary fixed number of clusters and propose polynomial constant-factor approximation algorithms for this case.
KW - Approximation algorithm
KW - Bounded scatter
KW - Clustering
KW - Euclidean space
KW - Max-min problem
KW - NP-hardness
UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-85164933301&origin=inward&txGid=ca3551a91804151187da7c4d66c24d74
UR - https://www.mendeley.com/catalogue/60315967-5a2e-32d3-bf33-bb23943c144f/
U2 - 10.1007/978-3-031-35305-5_6
DO - 10.1007/978-3-031-35305-5_6
M3 - Conference contribution
SN - 9783031353048
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 85
EP - 100
BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PB - Springer Science and Business Media Deutschland GmbH
ER -
ID: 59126398