Standard

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

Harvard

Khandeev, V & Neshchadim, S 2023, Constant-Factor Approximation Algorithms for Some Maximin Multi-clustering Problems. in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13930 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 85-100. https://doi.org/10.1007/978-3-031-35305-5_6

APA

Khandeev, V., & Neshchadim, S. (2023). Constant-Factor Approximation Algorithms for Some Maximin Multi-clustering Problems. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 85-100). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13930 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-35305-5_6

Vancouver

Khandeev V, Neshchadim S. Constant-Factor Approximation Algorithms for Some Maximin Multi-clustering Problems. In 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)). doi: 10.1007/978-3-031-35305-5_6

Author

Khandeev, Vladimir ; Neshchadim, Sergey. / Constant-Factor Approximation Algorithms for Some Maximin Multi-clustering Problems. 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. pp. 85-100 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{317798f50efd42e49bd56dbf04622970,
title = "Constant-Factor Approximation Algorithms for Some Maximin Multi-clustering Problems",
abstract = "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{\textquoteright}s cardinality under constraint on each cluster{\textquoteright}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.",
keywords = "Approximation algorithm, Bounded scatter, Clustering, Euclidean space, Max-min problem, NP-hardness",
author = "Vladimir Khandeev and Sergey Neshchadim",
note = "The study presented was supported by the Russian Academy of Science (the Program of basic research), project FWNF-2022-0015.",
year = "2023",
doi = "10.1007/978-3-031-35305-5_6",
language = "English",
isbn = "9783031353048",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "85--100",
booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
address = "Germany",

}

RIS

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