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 -