Standard
Max-Min Problems of Searching for Two Disjoint Subsets. / Khandeev, Vladimir; Neshchadim, Sergey.
Optimization and Applications - 12th International Conference, OPTIMA 2021, Proceedings. ed. / Nicholas N. Olenev; Yuri G. Evtushenko; Milojica Jaćimović; Michael Khachay; Vlasta Malkova. Springer Science and Business Media Deutschland GmbH, 2021. p. 231-245 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13078 LNCS).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Harvard
Khandeev, V & Neshchadim, S 2021,
Max-Min Problems of Searching for Two Disjoint Subsets. in NN Olenev, YG Evtushenko, M Jaćimović, M Khachay & V Malkova (eds),
Optimization and Applications - 12th International Conference, OPTIMA 2021, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13078 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 231-245, 12th International Conference on Optimization and Applications, OPTIMA 2021, Virtual, Online,
27.09.2021.
https://doi.org/10.1007/978-3-030-91059-4_17
APA
Khandeev, V., & Neshchadim, S. (2021).
Max-Min Problems of Searching for Two Disjoint Subsets. In N. N. Olenev, Y. G. Evtushenko, M. Jaćimović, M. Khachay, & V. Malkova (Eds.),
Optimization and Applications - 12th International Conference, OPTIMA 2021, Proceedings (pp. 231-245). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13078 LNCS). Springer Science and Business Media Deutschland GmbH.
https://doi.org/10.1007/978-3-030-91059-4_17
Vancouver
Khandeev V, Neshchadim S.
Max-Min Problems of Searching for Two Disjoint Subsets. In Olenev NN, Evtushenko YG, Jaćimović M, Khachay M, Malkova V, editors, Optimization and Applications - 12th International Conference, OPTIMA 2021, Proceedings. Springer Science and Business Media Deutschland GmbH. 2021. p. 231-245. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-91059-4_17
Author
Khandeev, Vladimir ; Neshchadim, Sergey. /
Max-Min Problems of Searching for Two Disjoint Subsets. Optimization and Applications - 12th International Conference, OPTIMA 2021, Proceedings. editor / Nicholas N. Olenev ; Yuri G. Evtushenko ; Milojica Jaćimović ; Michael Khachay ; Vlasta Malkova. Springer Science and Business Media Deutschland GmbH, 2021. pp. 231-245 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
BibTeX
@inproceedings{96ce56345bf64b10a4c89828f9f12319,
title = "Max-Min Problems of Searching for Two Disjoint Subsets",
abstract = "The work considers three problems of searching for two disjoint subsets among a finite set of points in Euclidean space. In all three problems, it is required to maximize the minimal size of these subsets so that in each cluster, the total intra-cluster scatter of points relative to the cluster center does not exceed a predetermined threshold. In the first problem, the centers of the clusters are fixed points of Euclidean space and are given as input. In the second one, centers are unknown, but they belong to the initial set. In the last problem, the center of the cluster is the arithmetic mean of all its elements. Earlier works considered problems with constraints on the quadratic intra-cluster scatter. Quadratic analogs of the first two problems were proven to be NP-hard even in the one-dimensional case. For the third analog, the complexity remains unknown. The main result of the work are proofs of NP-hardness of all considered problems even in the one-dimensional case.",
keywords = "Bounded scatter, Clustering, Euclidean space, Max-min problem, NP-hardness",
author = "Vladimir Khandeev and Sergey Neshchadim",
note = "Publisher Copyright: {\textcopyright} 2021, Springer Nature Switzerland AG.; 12th International Conference on Optimization and Applications, OPTIMA 2021 ; Conference date: 27-09-2021 Through 01-10-2021",
year = "2021",
doi = "10.1007/978-3-030-91059-4_17",
language = "English",
isbn = "9783030910587",
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 = "231--245",
editor = "Olenev, {Nicholas N.} and Evtushenko, {Yuri G.} and Milojica Ja{\'c}imovi{\'c} and Michael Khachay and Vlasta Malkova",
booktitle = "Optimization and Applications - 12th International Conference, OPTIMA 2021, Proceedings",
address = "Germany",
}
RIS
TY - GEN
T1 - Max-Min Problems of Searching for Two Disjoint Subsets
AU - Khandeev, Vladimir
AU - Neshchadim, Sergey
N1 - Publisher Copyright:
© 2021, Springer Nature Switzerland AG.
PY - 2021
Y1 - 2021
N2 - The work considers three problems of searching for two disjoint subsets among a finite set of points in Euclidean space. In all three problems, it is required to maximize the minimal size of these subsets so that in each cluster, the total intra-cluster scatter of points relative to the cluster center does not exceed a predetermined threshold. In the first problem, the centers of the clusters are fixed points of Euclidean space and are given as input. In the second one, centers are unknown, but they belong to the initial set. In the last problem, the center of the cluster is the arithmetic mean of all its elements. Earlier works considered problems with constraints on the quadratic intra-cluster scatter. Quadratic analogs of the first two problems were proven to be NP-hard even in the one-dimensional case. For the third analog, the complexity remains unknown. The main result of the work are proofs of NP-hardness of all considered problems even in the one-dimensional case.
AB - The work considers three problems of searching for two disjoint subsets among a finite set of points in Euclidean space. In all three problems, it is required to maximize the minimal size of these subsets so that in each cluster, the total intra-cluster scatter of points relative to the cluster center does not exceed a predetermined threshold. In the first problem, the centers of the clusters are fixed points of Euclidean space and are given as input. In the second one, centers are unknown, but they belong to the initial set. In the last problem, the center of the cluster is the arithmetic mean of all its elements. Earlier works considered problems with constraints on the quadratic intra-cluster scatter. Quadratic analogs of the first two problems were proven to be NP-hard even in the one-dimensional case. For the third analog, the complexity remains unknown. The main result of the work are proofs of NP-hardness of all considered problems even in the one-dimensional case.
KW - Bounded scatter
KW - Clustering
KW - Euclidean space
KW - Max-min problem
KW - NP-hardness
UR - http://www.scopus.com/inward/record.url?scp=85120075368&partnerID=8YFLogxK
UR - https://www.mendeley.com/catalogue/5921a92b-0ed3-33e1-9c18-c841f4c45959/
U2 - 10.1007/978-3-030-91059-4_17
DO - 10.1007/978-3-030-91059-4_17
M3 - Conference contribution
AN - SCOPUS:85120075368
SN - 9783030910587
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 231
EP - 245
BT - Optimization and Applications - 12th International Conference, OPTIMA 2021, Proceedings
A2 - Olenev, Nicholas N.
A2 - Evtushenko, Yuri G.
A2 - Jaćimović, Milojica
A2 - Khachay, Michael
A2 - Malkova, Vlasta
PB - Springer Science and Business Media Deutschland GmbH
T2 - 12th International Conference on Optimization and Applications, OPTIMA 2021
Y2 - 27 September 2021 through 1 October 2021
ER -
