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 proceedingConference contributionResearchpeer-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_28

APA

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_28

Vancouver

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 -

ID: 18489624