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

DOI10.1007/S10472-019-09623-ZMaRDI QIDQ2294598zbMATH OpenOpenAlexWikidataFDO

Authors A. V. Kel'manov, S. A. Khamidullin, Vladimir Khandeev, Artem Pyatkin

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

exact algorithmquadratic variationEuclidean spacepseudopolynomial timelongest subsequencelargest subset

Mathematics Subject Classification ID

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

Recommendations

• A Sub-Quadratic Algorithm for the Longest Common Increasing Subsequence Problem.
• Exact algorithms for the repetition-bounded longest common subsequence problem
• Exact algorithms for the bounded repetition longest common subsequence problem
• A Faster Subquadratic Algorithm for the Longest Common Increasing Subsequence Problem
• Algorithms for Computing the Longest Parameterized Common Subsequence
• An Algorithm for a Generalized Maximum Subsequence Problem
• Algorithms for Computing Variants of the Longest Common Subsequence Problem
• An almost-linear time and linear space algorithm for the longest common subsequence problem
• Efficient algorithms for the longest common subsequence problem with sequential substring constraints
• On two variants of the longest increasing subsequence problem

Cites work

• Accurate pseudopolynomial-time algorithms for certain NP-hard problems of searching for a vector subsequence
• An FPTAS for a vector subset search problem
• An approximation scheme for a problem of search for a vector subset
• An approximation scheme for the problem of finding a subsequence
• An introduction to statistical learning. With applications in R
• Approximation algorithms for some intractable problems of choosing a vector subsequence
• Cluster analysis and mathematical programming
• Clustering of time series data -- a survey
• Data mining. The textbook
• Finding k points with minimum diameter and related problems
• On the complexity of certain problems of choosing subset of vectors
• Pattern recognition and machine learning.
• 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
• Robust methods for data reduction

Cited in

(1)

• Near Linear Time Construction of an Approximate Index for All Maximum Consecutive Sub-sums of a Sequence

Describes a project that uses

Uses Software

• PRMLT

This page was built for publication: Exact algorithms for two integer-valued problems of searching for the largest subset and longest subsequence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2294598)