Exact algorithms for two integer-valued problems of searching for the largest subset and longest subsequence

DOI10.1007/s10472-019-09623-zzbMath1431.90132OpenAlexW2924034761WikidataQ128178116 ScholiaQ128178116MaRDI QIDQ2294598

Artem V. Pyatkin, Vladimir Khandeev, Sergey Khamidullin, Alexander Kel'Manov

Publication date: 11 February 2020

Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10472-019-09623-z

zbMATH Keywords

Euclidean spacequadratic variationexact algorithmpseudopolynomial timelongest subsequencelargest subset

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05) Combinatorial optimization (90C27)

Uses Software

• PRMLT

Cites Work

• Unnamed Item
• Unnamed Item
• Cluster analysis and mathematical programming
• Posterior detection of a given number of identical subsequences in a quasi-periodic sequence
• Pseudopolynomial algorithms for certain computationally hard vector subset and cluster analysis problems
• Clustering of time series data -- a survey
• Точные псевдополиномиальные алгоритмы для некоторых труднорешаемых задач поиска подпоследовательности векторов
• Finding k points with minimum diameter and related problems
• An Approximation Scheme for the Problem of Finding a Subsequence
• An Introduction to Statistical Learning
• Robust Methods for Data Reduction
• Data Mining
• An approximation scheme for a problem of search for a vector subset
• Approximation algorithms for some intractable problems of choosing a vector subsequence
• An FPTAS for a vector subset search problem