An Approximation Scheme for the Problem of Finding a Subsequence

DOI10.1134/S1995423917040036zbMath1399.68314OpenAlexW2790737724MaRDI QIDQ4636841

S. M. Romanchenko, Alexander Kel'Manov, Sergey 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 spaceNP-hardnesssequenceFPTASminimum sum of squared distances

Mathematics Subject Classification ID

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

Related Items (1)

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

This page was built for publication: An Approximation Scheme for the Problem of Finding a Subsequence