Accurate pseudopolynomial-time algorithms for certain NP-hard problems of searching for a vector subsequence

DOI10.7868/S0044466913010055zbMATH Open1274.90517OpenAlexW2326291150MaRDI QIDQ2838802FDOQ2838802

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

Publication date: 3 July 2013

Published in: Zhurnal Vychislitel'noĭ Matematiki i Matematicheskoĭ Fiziki (Search for Journal in Brave)

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

Recommendations

• The problem of finding a subset of vectors with maximal total weight
• On the complexity of certain problems of choosing subset of vectors
• Pseudopolynomial algorithms for certain computationally hard vector subset and cluster analysis problems
• Approximation algorithms for some intractable problems of choosing a vector subsequence
• An approximation scheme for the problem of finding a subsequence

zbMATH Keywords

NP-hard problemsaccurate pseudopolynomial algorithmsearching for a vector subsequence

Mathematics Subject Classification ID

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

Cited In (5)

• A randomized algorithm for two-cluster partition of a set of vectors
• Approximation algorithms for some intractable problems of choosing a vector subsequence
• 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
• Pseudopolynomial algorithms for certain computationally hard vector subset and cluster analysis problems

This page was built for publication: Accurate pseudopolynomial-time algorithms for certain NP-hard problems of searching for a vector subsequence

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