Standard
Exact algorithms for the special cases of two hard to solve problems of searching for the largest subset. / Kel’manov, Alexander; Khandeev, Vladimir; Panasenko, Anna.
Analysis of Images, Social Networks and Texts - 7th International Conference, AIST 2018, Revised Selected Papers. ed. / Alexander Panchenko; Wil M. van der Aalst; Michael Khachay; Panos M. Pardalos; Vladimir Batagelj; Natalia Loukachevitch; Goran Glavaš; Dmitry I. Ignatov; Sergei O. Kuznetsov; Olessia Koltsova; Irina A. Lomazova; Andrey V. Savchenko; Amedeo Napoli; Marcello Pelillo. Springer-Verlag GmbH and Co. KG, 2018. p. 294-304 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11179 LNCS).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Harvard
Kel’manov, A
, Khandeev, V & Panasenko, A 2018,
Exact algorithms for the special cases of two hard to solve problems of searching for the largest subset. in A Panchenko, WM van der Aalst, M Khachay, PM Pardalos, V Batagelj, N Loukachevitch, G Glavaš, DI Ignatov, SO Kuznetsov, O Koltsova, IA Lomazova, AV Savchenko, A Napoli & M Pelillo (eds),
Analysis of Images, Social Networks and Texts - 7th International Conference, AIST 2018, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11179 LNCS, Springer-Verlag GmbH and Co. KG, pp. 294-304, 7th International Conference on Analysis of Images, Social Networks and Texts, AIST 2018, Moscow, Russian Federation,
05.07.2018.
https://doi.org/10.1007/978-3-030-11027-7_28APA
Kel’manov, A.
, Khandeev, V., & Panasenko, A. (2018).
Exact algorithms for the special cases of two hard to solve problems of searching for the largest subset. In A. Panchenko, W. M. van der Aalst, M. Khachay, P. M. Pardalos, V. Batagelj, N. Loukachevitch, G. Glavaš, D. I. Ignatov, S. O. Kuznetsov, O. Koltsova, I. A. Lomazova, A. V. Savchenko, A. Napoli, & M. Pelillo (Eds.),
Analysis of Images, Social Networks and Texts - 7th International Conference, AIST 2018, Revised Selected Papers (pp. 294-304). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11179 LNCS). Springer-Verlag GmbH and Co. KG.
https://doi.org/10.1007/978-3-030-11027-7_28Vancouver
Kel’manov A
, Khandeev V, Panasenko A.
Exact algorithms for the special cases of two hard to solve problems of searching for the largest subset. In Panchenko A, van der Aalst WM, Khachay M, Pardalos PM, Batagelj V, Loukachevitch N, Glavaš G, Ignatov DI, Kuznetsov SO, Koltsova O, Lomazova IA, Savchenko AV, Napoli A, Pelillo M, editors, Analysis of Images, Social Networks and Texts - 7th International Conference, AIST 2018, Revised Selected Papers. Springer-Verlag GmbH and Co. KG. 2018. p. 294-304. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-11027-7_28
Author
Kel’manov, Alexander
; Khandeev, Vladimir ; Panasenko, Anna. /
Exact algorithms for the special cases of two hard to solve problems of searching for the largest subset. Analysis of Images, Social Networks and Texts - 7th International Conference, AIST 2018, Revised Selected Papers. editor / Alexander Panchenko ; Wil M. van der Aalst ; Michael Khachay ; Panos M. Pardalos ; Vladimir Batagelj ; Natalia Loukachevitch ; Goran Glavaš ; Dmitry I. Ignatov ; Sergei O. Kuznetsov ; Olessia Koltsova ; Irina A. Lomazova ; Andrey V. Savchenko ; Amedeo Napoli ; Marcello Pelillo. Springer-Verlag GmbH and Co. KG, 2018. pp. 294-304 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
BibTeX
@inproceedings{ecba9e10162e4bc591a955d2dad4eea7,
title = "Exact algorithms for the special cases of two hard to solve problems of searching for the largest subset",
abstract = "We consider two problems of searching for the largest subset in a finite set of points in Euclidean space. Both problems have applications, in particular, in data analysis and data approximation. In each problem, an input set and a positive real number are given and it is required to find a subset (i.e., a cluster) of the largest size under a constraint on the value of a quadratic function. The points in the input set which are outside the sought subset are treated as a second cluster. In the first problem, the function in the constraint is the sum over both clusters of the intracluster sums of the squared distances between the elements of the clusters and their centers. The center of the first (i.e., sought) cluster is unknown and determined as the centroid, while the center of the second one is fixed in a given point in Euclidean space (without loss of generality in the origin). In the second problem, the function in the constraint is the sum over both clusters of the weighted intracluster sums of the squared distances between the elements of the clusters and their centers. As in the first problem, the center of the first cluster is unknown and determined as the centroid, while the center of the second one is fixed in the origin. In this paper, we show that both problems are strongly NP-hard. Also, we present exact algorithms for the cases of these problems in which the input points have integer components. If the space dimension is bounded by some constant, the algorithms are pseudopolynomial.",
keywords = "2-clustering, Euclidean space, Exact algorithm, Largest subset, NP-hardness, Pseudopolynomial-time solvability",
author = "Alexander Kel{\textquoteright}manov and Vladimir Khandeev and Anna Panasenko",
year = "2018",
month = jan,
day = "1",
doi = "10.1007/978-3-030-11027-7_28",
language = "English",
isbn = "9783030110260",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer-Verlag GmbH and Co. KG",
pages = "294--304",
editor = "Alexander Panchenko and {van der Aalst}, {Wil M.} and Michael Khachay and Pardalos, {Panos M.} and Vladimir Batagelj and Natalia Loukachevitch and Goran Glava{\v s} and Ignatov, {Dmitry I.} and Kuznetsov, {Sergei O.} and Olessia Koltsova and Lomazova, {Irina A.} and Savchenko, {Andrey V.} and Amedeo Napoli and Marcello Pelillo",
booktitle = "Analysis of Images, Social Networks and Texts - 7th International Conference, AIST 2018, Revised Selected Papers",
address = "Germany",
note = "7th International Conference on Analysis of Images, Social Networks and Texts, AIST 2018 ; Conference date: 05-07-2018 Through 07-07-2018",
}
RIS
TY - GEN
T1 - Exact algorithms for the special cases of two hard to solve problems of searching for the largest subset
AU - Kel’manov, Alexander
AU - Khandeev, Vladimir
AU - Panasenko, Anna
PY - 2018/1/1
Y1 - 2018/1/1
N2 - We consider two problems of searching for the largest subset in a finite set of points in Euclidean space. Both problems have applications, in particular, in data analysis and data approximation. In each problem, an input set and a positive real number are given and it is required to find a subset (i.e., a cluster) of the largest size under a constraint on the value of a quadratic function. The points in the input set which are outside the sought subset are treated as a second cluster. In the first problem, the function in the constraint is the sum over both clusters of the intracluster sums of the squared distances between the elements of the clusters and their centers. The center of the first (i.e., sought) cluster is unknown and determined as the centroid, while the center of the second one is fixed in a given point in Euclidean space (without loss of generality in the origin). In the second problem, the function in the constraint is the sum over both clusters of the weighted intracluster sums of the squared distances between the elements of the clusters and their centers. As in the first problem, the center of the first cluster is unknown and determined as the centroid, while the center of the second one is fixed in the origin. In this paper, we show that both problems are strongly NP-hard. Also, we present exact algorithms for the cases of these problems in which the input points have integer components. If the space dimension is bounded by some constant, the algorithms are pseudopolynomial.
AB - We consider two problems of searching for the largest subset in a finite set of points in Euclidean space. Both problems have applications, in particular, in data analysis and data approximation. In each problem, an input set and a positive real number are given and it is required to find a subset (i.e., a cluster) of the largest size under a constraint on the value of a quadratic function. The points in the input set which are outside the sought subset are treated as a second cluster. In the first problem, the function in the constraint is the sum over both clusters of the intracluster sums of the squared distances between the elements of the clusters and their centers. The center of the first (i.e., sought) cluster is unknown and determined as the centroid, while the center of the second one is fixed in a given point in Euclidean space (without loss of generality in the origin). In the second problem, the function in the constraint is the sum over both clusters of the weighted intracluster sums of the squared distances between the elements of the clusters and their centers. As in the first problem, the center of the first cluster is unknown and determined as the centroid, while the center of the second one is fixed in the origin. In this paper, we show that both problems are strongly NP-hard. Also, we present exact algorithms for the cases of these problems in which the input points have integer components. If the space dimension is bounded by some constant, the algorithms are pseudopolynomial.
KW - 2-clustering
KW - Euclidean space
KW - Exact algorithm
KW - Largest subset
KW - NP-hardness
KW - Pseudopolynomial-time solvability
UR - http://www.scopus.com/inward/record.url?scp=85059959288&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-11027-7_28
DO - 10.1007/978-3-030-11027-7_28
M3 - Conference contribution
AN - SCOPUS:85059959288
SN - 9783030110260
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 294
EP - 304
BT - Analysis of Images, Social Networks and Texts - 7th International Conference, AIST 2018, Revised Selected Papers
A2 - Panchenko, Alexander
A2 - van der Aalst, Wil M.
A2 - Khachay, Michael
A2 - Pardalos, Panos M.
A2 - Batagelj, Vladimir
A2 - Loukachevitch, Natalia
A2 - Glavaš, Goran
A2 - Ignatov, Dmitry I.
A2 - Kuznetsov, Sergei O.
A2 - Koltsova, Olessia
A2 - Lomazova, Irina A.
A2 - Savchenko, Andrey V.
A2 - Napoli, Amedeo
A2 - Pelillo, Marcello
PB - Springer-Verlag GmbH and Co. KG
T2 - 7th International Conference on Analysis of Images, Social Networks and Texts, AIST 2018
Y2 - 5 July 2018 through 7 July 2018
ER -
