On the complexity of certain problems of choosing subset of vectors

MaRDI QIDQ2836761zbMATH OpenFDO

Authors A. V. Kel'manov, Artem Pyatkin

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/v52/i12/p2284

zbMATH Keywords

algorithmic complexitychoice of subsequence of vectorsminimum of sum of square of distancesNP-completeness

Mathematics Subject Classification ID

Quadratic programming (90C20)

Review text

The NP-completeness is proved for some choices of subsequences of the vector sequence of some Euclidean space. The required subsequence is supposed to contain fixed number of vectors which are close each other with respect to the criterion of minimum of sums of distances. The choice of vectors is constrained.

Recommendations

• NP-completeness of some problems of a vectors subset choice
• On complexity of the problem of choosing a vector subset with maximal sum length
• On a variant of the problem of choosing a vector subset
• The problem of finding a subset of vectors with maximal total weight
• Easy NP-hardness Proofs of Some Subset Choice Problems

Cited in

(15)

• 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
• On the complexity of some data analysis problems
• On complexity of the problem of choosing a vector subset with maximal sum length
• NP-completeness of some problems of a vectors subset choice
• The problem of finding a subset of vectors with maximal total weight
• scientific article; zbMATH DE number 6004955 (Why is no real title available?)
• On a variant of the problem of choosing a vector subset
• scientific article; zbMATH DE number 6004969 (Why is no real title available?)
• On the complexity of some Euclidean optimal summing problems
• Easy NP-hardness Proofs of Some Subset Choice Problems
• On the complexity and approximability of some Euclidean optimal summing problems
• Approximation algorithms for some intractable problems of choosing a vector subsequence
• Complexity and algorithms for finding a subset of vectors with the longest sum
• Complexity of optimal vector code generation

This page was built for publication: On the complexity of certain problems of choosing subset of vectors

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