Standard
NP-hardness of some max-min clustering problems. / Kel’manov, Alexander; Khandeev, Vladimir; Pyatkin, Artem.
Optimization and Applications - 9th International Conference, OPTIMA 2018, Revised Selected Papers. ed. / Yury Kochetov; Michael Khachay; Yury Evtushenko; Vlasta Malkova; Mikhail Posypkin; Milojica Jacimovic. Springer-Verlag GmbH and Co. KG, 2019. p. 144-154 (Communications in Computer and Information Science; Vol. 974).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Harvard
Kel’manov, A
, Khandeev, V & Pyatkin, A 2019,
NP-hardness of some max-min clustering problems. in Y Kochetov, M Khachay, Y Evtushenko, V Malkova, M Posypkin & M Jacimovic (eds),
Optimization and Applications - 9th International Conference, OPTIMA 2018, Revised Selected Papers. Communications in Computer and Information Science, vol. 974, Springer-Verlag GmbH and Co. KG, pp. 144-154, 9th International Conference on Optimization and Applications, OPTIMA 2018, Petrovac, Montenegro,
01.10.2018.
https://doi.org/10.1007/978-3-030-10934-9_11APA
Kel’manov, A.
, Khandeev, V., & Pyatkin, A. (2019).
NP-hardness of some max-min clustering problems. In Y. Kochetov, M. Khachay, Y. Evtushenko, V. Malkova, M. Posypkin, & M. Jacimovic (Eds.),
Optimization and Applications - 9th International Conference, OPTIMA 2018, Revised Selected Papers (pp. 144-154). (Communications in Computer and Information Science; Vol. 974). Springer-Verlag GmbH and Co. KG.
https://doi.org/10.1007/978-3-030-10934-9_11Vancouver
Kel’manov A
, Khandeev V, Pyatkin A.
NP-hardness of some max-min clustering problems. In Kochetov Y, Khachay M, Evtushenko Y, Malkova V, Posypkin M, Jacimovic M, editors, Optimization and Applications - 9th International Conference, OPTIMA 2018, Revised Selected Papers. Springer-Verlag GmbH and Co. KG. 2019. p. 144-154. (Communications in Computer and Information Science). doi: 10.1007/978-3-030-10934-9_11
Author
Kel’manov, Alexander
; Khandeev, Vladimir ; Pyatkin, Artem. /
NP-hardness of some max-min clustering problems. Optimization and Applications - 9th International Conference, OPTIMA 2018, Revised Selected Papers. editor / Yury Kochetov ; Michael Khachay ; Yury Evtushenko ; Vlasta Malkova ; Mikhail Posypkin ; Milojica Jacimovic. Springer-Verlag GmbH and Co. KG, 2019. pp. 144-154 (Communications in Computer and Information Science).
BibTeX
@inproceedings{1711a0c75fab4aefb931ed8d008add6d,
title = "NP-hardness of some max-min clustering problems",
abstract = "We consider some consimilar problems of searching for disjoint clusters in the finite set of points in Euclidean space. The goal is to maximize the minimum subset size so that the value of each intracluster quadratic variation would not exceed a given constant. We prove that all considered problems are NP-hard even on a line.",
keywords = "Clustering, Euclidean space, Max-Min problem, NP-hardness, Quadratic variation",
author = "Alexander Kel{\textquoteright}manov and Vladimir Khandeev and Artem Pyatkin",
note = "Publisher Copyright: {\textcopyright} Springer Nature Switzerland AG 2019.; 9th International Conference on Optimization and Applications, OPTIMA 2018 ; Conference date: 01-10-2018 Through 05-10-2018",
year = "2019",
month = jan,
day = "1",
doi = "10.1007/978-3-030-10934-9_11",
language = "English",
isbn = "9783030109332",
series = "Communications in Computer and Information Science",
publisher = "Springer-Verlag GmbH and Co. KG",
pages = "144--154",
editor = "Yury Kochetov and Michael Khachay and Yury Evtushenko and Vlasta Malkova and Mikhail Posypkin and Milojica Jacimovic",
booktitle = "Optimization and Applications - 9th International Conference, OPTIMA 2018, Revised Selected Papers",
address = "Germany",
}
RIS
TY - GEN
T1 - NP-hardness of some max-min clustering problems
AU - Kel’manov, Alexander
AU - Khandeev, Vladimir
AU - Pyatkin, Artem
N1 - Publisher Copyright:
© Springer Nature Switzerland AG 2019.
PY - 2019/1/1
Y1 - 2019/1/1
N2 - We consider some consimilar problems of searching for disjoint clusters in the finite set of points in Euclidean space. The goal is to maximize the minimum subset size so that the value of each intracluster quadratic variation would not exceed a given constant. We prove that all considered problems are NP-hard even on a line.
AB - We consider some consimilar problems of searching for disjoint clusters in the finite set of points in Euclidean space. The goal is to maximize the minimum subset size so that the value of each intracluster quadratic variation would not exceed a given constant. We prove that all considered problems are NP-hard even on a line.
KW - Clustering
KW - Euclidean space
KW - Max-Min problem
KW - NP-hardness
KW - Quadratic variation
UR - http://www.scopus.com/inward/record.url?scp=85061209809&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-10934-9_11
DO - 10.1007/978-3-030-10934-9_11
M3 - Conference contribution
AN - SCOPUS:85061209809
SN - 9783030109332
T3 - Communications in Computer and Information Science
SP - 144
EP - 154
BT - Optimization and Applications - 9th International Conference, OPTIMA 2018, Revised Selected Papers
A2 - Kochetov, Yury
A2 - Khachay, Michael
A2 - Evtushenko, Yury
A2 - Malkova, Vlasta
A2 - Posypkin, Mikhail
A2 - Jacimovic, Milojica
PB - Springer-Verlag GmbH and Co. KG
T2 - 9th International Conference on Optimization and Applications, OPTIMA 2018
Y2 - 1 October 2018 through 5 October 2018
ER -
