On the complexity of certain problems of choosing subset of vectors (Q2836761)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 6183582
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | On the complexity of certain problems of choosing subset of vectors |
scientific article; zbMATH DE number 6183582 |
Statements
3 July 2013
0 references
choice of subsequence of vectors
0 references
minimum of sum of square of distances
0 references
algorithmic complexity
0 references
NP-completeness
0 references
On the complexity of certain problems of choosing subset of vectors (English)
0 references
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.
0 references
0.9382138848304749
0 references
0.8863698244094849
0 references
0.8835613131523132
0 references
0.8405821323394775
0 references
0.8380147218704224
0 references
