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

DOI10.7868/S0044466913010055MaRDI QIDQ2838802zbMATH OpenOpenAlexFDO

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

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)

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

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)