Approximation algorithms for some intractable problems of choosing a vector subsequence

DOI10.1134/S1990478912040059zbMATH Open1324.68246OpenAlexW2078342465MaRDI QIDQ5263772FDOQ5263772

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

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

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)

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)