Approximation algorithms for some intractable problems of choosing a vector subsequence

DOI10.1134/S1990478912040059MaRDI QIDQ5263772zbMATH OpenOpenAlexFDO

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

Publication date 17 July 2015

Published in Journal of Applied and Industrial Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

cluster analysisNP-hardnesssearch for a vector subsetefficient approximation algorithmminimum sum of squares of distances

Mathematics Subject Classification ID

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

Recommendations

• On the complexity of certain problems of choosing subset of vectors
• The problem of finding a subset of vectors with maximal total weight
• An approximation scheme for the problem of finding a subsequence
• An approximation algorithm for solving the problem of the search of a subset of vectors
• Accurate pseudopolynomial-time algorithms for certain NP-hard problems of searching for a vector subsequence

Cited in

(3)

• An approximation scheme for the problem of finding a subsequence
• Exact algorithms for two integer-valued problems of searching for the largest subset and longest subsequence
• Accurate pseudopolynomial-time algorithms for certain NP-hard problems of searching for a vector subsequence

This page was built for publication: Approximation algorithms for some intractable problems of choosing a vector subsequence

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