An approximation scheme for the problem of finding a subsequence

DOI10.1134/S1995423917040036MaRDI QIDQ4636841zbMATH OpenOpenAlexFDO

Authors S. M. Romanchenko, A. V. Kel'manov, S. A. Khamidullin

Publication date 20 April 2018

Published in Numerical Analysis and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1134/s1995423917040036

zbMATH Keywords

Euclidean spaceFPTASminimum sum of squared distancesNP-hardnesssequence

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Algorithms on strings (68W32)

Recommendations

• Approximation algorithms for some intractable problems of choosing a vector subsequence
• A fully polynomial-time approximation scheme for a sequence 2-cluster partitioning problem
• Approximation algorithm for the problem of partitioning a sequence into clusters
• An FPTAS for a vector subset search problem
• An approximation algorithm for a problem of partitioning a sequence into clusters with constraints on their cardinalities

Cited in

(8)

• Exact algorithms for two integer-valued problems of searching for the largest subset and longest subsequence
• Finding least-weight subsequences with fewer processors
• Approximating the maximum consecutive subsums of a sequence
• Accurate pseudopolynomial-time algorithms for certain NP-hard problems of searching for a vector subsequence
• Near Linear Time Construction of an Approximate Index for All Maximum Consecutive Sub-sums of a Sequence
• Approximation algorithms for some intractable problems of choosing a vector subsequence
• An FPTAS for a vector subset search problem
• The complexity of finding SUBSEQ(A)

This page was built for publication: An approximation scheme for the problem of finding a subsequence

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