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

DOI10.1007/S10472-019-09623-ZzbMATH Open1431.90132OpenAlexW2924034761WikidataQ128178116 ScholiaQ128178116MaRDI QIDQ2294598FDOQ2294598

Artem Pyatkin, Vladimir Khandeev, S. A. Khamidullin, A. V. 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

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

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)

Cites Work

• An Introduction to Statistical Learning
• Pattern recognition and machine learning.
• Clustering of time series data -- a survey
• Cluster analysis and mathematical programming
• Finding k points with minimum diameter and related problems
• On the complexity of certain problems of choosing subset of vectors
• Pseudopolynomial algorithms for certain computationally hard vector subset and cluster analysis problems
• An approximation scheme for a problem of search for a vector subset
• Robust Methods for Data Reduction
• Posterior detection of a given number of identical subsequences in a quasi-periodic sequence
• Data Mining
• An Approximation Scheme for the Problem of Finding a Subsequence
• An FPTAS for a vector subset search problem
• Accurate pseudopolynomial-time algorithms for certain NP-hard problems of searching for a vector subsequence
• Approximation algorithms for some intractable problems of choosing a vector subsequence

Cited In (1)

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

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)