Точные псевдополиномиальные алгоритмы для некоторых труднорешаемых задач поиска подпоследовательности векторов

DOI10.7868/S0044466913010055zbMath1274.90517OpenAlexW2326291150MaRDI QIDQ2838802

S. M. Romanchenko, Sergey Khamidullin, Alexander Kel'Manov

Publication date: 3 July 2013

Published in: Журнал вычислительной математики и математической физики (Search for Journal in Brave)

Full work available at URL: http://mathnet.ru/eng/zvmmf/v53/i1/p143

zbMATH Keywords

NP-hard problemsaccurate pseudopolynomial algorithmsearching for a vector subsequence

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Quadratic programming (90C20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

An exact pseudopolynomial algorithm for a problem of the two-cluster partitioning of a set of vectors ⋮ Exact algorithms for two integer-valued problems of searching for the largest subset and longest subsequence ⋮ A randomized algorithm for two-cluster partition of a set of vectors

This page was built for publication: Точные псевдополиномиальные алгоритмы для некоторых труднорешаемых задач поиска подпоследовательности векторов