Research output: Contribution to journal › Article › peer-review
Exact algorithms for two integer-valued problems of searching for the largest subset and longest subsequence. / Kel’manov, Alexander; Khamidullin, Sergey; Khandeev, Vladimir et al.
In: Annals of Mathematics and Artificial Intelligence, Vol. 88, No. 1-3, 01.03.2020, p. 157-168.Research output: Contribution to journal › Article › peer-review
}
TY - JOUR
T1 - Exact algorithms for two integer-valued problems of searching for the largest subset and longest subsequence
AU - Kel’manov, Alexander
AU - Khamidullin, Sergey
AU - Khandeev, Vladimir
AU - Pyatkin, Artem
N1 - The study presented in Sections 2, 4 was supported by the Russian Science Foundation, project 16-11-10041. The study presented in Sections 3, 5 was supported by the Russian Foundation for Basic Research, projects 18-31-00398, 19-01-00308, and 19-07-00397, by the Russian Academy of Science (the Program of basic research), project 0314-2019-0015, and by the Russian Ministry of Science and Education under the 5-100 Excellence Programme.
PY - 2020/3/1
Y1 - 2020/3/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. The sum of squared distances between the elements of this subset and its unknown centroid (geometrical center) must not exceed a given value. This value is defined as 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. The restriction on the sum of squared distances is the same 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. The sum of squared distances between the elements of this subset and its unknown centroid (geometrical center) must not exceed a given value. This value is defined as 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. The restriction on the sum of squared distances is the same 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 - Largest subset
KW - Longest subsequence
KW - Pseudopolynomial time
KW - Quadratic variation
UR - http://www.scopus.com/inward/record.url?scp=85063124993&partnerID=8YFLogxK
U2 - 10.1007/s10472-019-09623-z
DO - 10.1007/s10472-019-09623-z
M3 - Article
AN - SCOPUS:85063124993
VL - 88
SP - 157
EP - 168
JO - Annals of Mathematics and Artificial Intelligence
JF - Annals of Mathematics and Artificial Intelligence
SN - 1012-2443
IS - 1-3
ER -
ID: 18958172