TY - GEN

T1 - Exact algorithms for two quadratic euclidean problems of searching for the largest subset and longest subsequence

AU - Kel’manov, Alexander

AU - Khamidullin, Sergey

AU - Khandeev, Vladimir

AU - Pyatkin, Artem

N1 - Publisher Copyright: © 2019, Springer Nature Switzerland AG.

PY - 2019/1/1

Y1 - 2019/1/1

N2 - The following two strongly NP-hard problems are considered. In the first problem, we need to find in the given finite set of points in Euclidean space the subset of largest size such that the sum of squared distances between the elements of this subset and its unknown centroid (geometrical center) does not exceed a given percentage of the sum of squared distances between the elements of the input set and its centroid. In the second problem, the input is a sequence (not a set) and we have some additional constraints on the indices of the elements of the chosen subsequence under the same restriction on the sum of squared distances as in the first problem. Both problems can be treated as data editing problems aimed to find similar elements and removal of extraneous (dissimilar) elements. We propose exact algorithms for the cases of both problems in which the input points have integer-valued coordinates. If the space dimension is bounded by some constant, our algorithms run in a pseudopolynomial time. Some results of numerical experiments illustrating the performance of the algorithms are presented.

AB - The following two strongly NP-hard problems are considered. In the first problem, we need to find in the given finite set of points in Euclidean space the subset of largest size such that the sum of squared distances between the elements of this subset and its unknown centroid (geometrical center) does not exceed a given percentage of the sum of squared distances between the elements of the input set and its centroid. In the second problem, the input is a sequence (not a set) and we have some additional constraints on the indices of the elements of the chosen subsequence under the same restriction on the sum of squared distances as in the first problem. Both problems can be treated as data editing problems aimed to find similar elements and removal of extraneous (dissimilar) elements. We propose exact algorithms for the cases of both problems in which the input points have integer-valued coordinates. If the space dimension is bounded by some constant, our algorithms run in a pseudopolynomial time. Some results of numerical experiments illustrating the performance of the algorithms are presented.

KW - Euclidean space

KW - Exact algorithm

KW - Fixed space dimension

KW - Integer coordinates

KW - Largest set

KW - Longest subsequence

KW - NP-hard problem

KW - Pseudopolynomial time

KW - Quadratic variation

UR - http://www.scopus.com/inward/record.url?scp=85059932946&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-05348-2_28

DO - 10.1007/978-3-030-05348-2_28

M3 - Conference contribution

AN - SCOPUS:85059932946

SN - 9783030053475

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 326

EP - 336

BT - Learning and Intelligent Optimization - 12th International Conference, LION 12, Revised Selected Papers

PB - Springer-Verlag GmbH and Co. KG

T2 - 12th International Conference on Learning and Intelligent Optimization, LION 12

Y2 - 10 June 2018 through 15 June 2018

ER -