Exact Algorithms for Two Quadratic Euclidean Problems of Searching for the Largest Subset and Longest Subsequence

被引：1

作者：

Kel'manov, Alexander ^{[1
,2
]}

Khamidullin, Sergey ^{[1
]}

Khandeev, Vladimir ^{[1
,2
]}

Pyatkin, Artem ^{[1
,2
]}

机构：

[1] Sobolev Inst Math, 4 Koptyug Ave, Novosibirsk 630090, Russia

[2] Novosibirsk State Univ, 2 Pirogova St, Novosibirsk 630090, Russia

来源：

LEARNING AND INTELLIGENT OPTIMIZATION, LION 12 | 2019年 / 11353卷

基金：

俄罗斯基础研究基金会; 俄罗斯科学基金会;

关键词：

Euclidean space; Largest set; Longest subsequence; Quadratic variation; NP-hard problem; Integer coordinates; Exact algorithm; Fixed space dimension; Pseudopolynomial time; TIME-SERIES DATA; CLUSTER-ANALYSIS;

D O I：

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

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

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.

引用

页码：326 / 336

页数：11

共 27 条

[21]

Kel'manov A.V., 2012, ZH VYCH MAT MAT FIZ, V52, P2284

[22]

Kuenzer C, 2015, REMOTE SENS DIGIT IM, V22, P427, DOI 10.1007/978-3-319-15967-6_20

[23] Clustering of time series data - a survey [J].

Liao, TW .

PATTERN RECOGNITION, 2005, 38 (11) :1857-1874

[24]

Osborne J., 2013, Best Practices in Data Cleaning, DOI [10.4135/9781452269948.n6, DOI 10.4135/9781452269948.N6]

[25]

Shenmaier V.V., 2012, J APPL IND MATH, V6, P381, DOI [10.1134/S1990478912030131, DOI 10.1134/S1990478912030131]

[26]

Shenmaier V. V., 2016, J APPL IND MATH, V10, P550

[27]

Shirkhorshidi AS, 2014, LECT NOTES COMPUT SC, V8583, P707, DOI 10.1007/978-3-319-09156-3_49

← 1 2 3 →