On the complexity of a search for a subset of ``similar vectors

DOI10.1134/S1064562408040273MaRDI QIDQ542229zbMATH OpenOpenAlexFDO

Authors A. V. Kel'manov, Artem Pyatkin

Publication date 8 June 2011

Published in Doklady Mathematics (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• On the complexity of some data analysis problems
• Recognition of a sequence as a structure containing series of recurring vectors from an alphabet
• An approximation algorithm for solving the problem of the search of a subset of vectors
• On one problem of searching for tuples of fragments in a numerical sequence
• Completeness of vector discrete optimization problems

Cited in

(19)

• On polynomial solvability of one quadratic Euclidean clustering problem on a line
• Polynomial-time solvability of the one-dimensional case of an NP-hard clustering problem
• A randomized algorithm for two-cluster partition of a set of vectors
• Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters
• Fully polynomial-time approximation scheme for a special case of a quadratic Euclidean 2-clustering problem
• On the complexity of some quadratic Euclidean 2-clustering problems
• An exact pseudopolynomial algorithm for a problem of the two-cluster partitioning of a set of vectors
• On the complexity of some Euclidean optimal summing problems
• NP-hardness of the Euclidean Max-Cut problem
• Easy NP-hardness Proofs of Some Subset Choice Problems
• An approximation polynomial-time algorithm for a sequence bi-clustering problem
• Exact algorithms of searching for the largest size cluster in two integer 2-clustering problems
• On the complexity and approximability of some Euclidean optimal summing problems
• The Problem K-Means and Given J-Centers: Polynomial Solvability in One Dimension
• Complexity of the weighted max-cut in Euclidean space
• Recognition of a sequence as a structure containing series of recurring vectors from an alphabet
• PTAS for \(p\)-means \(q\)-medoids \(r\)-given clustering problem
• PTAS for problems of vector choice and clustering with different centers
• NP-hardness of some quadratic Euclidean 2-clustering problems

This page was built for publication: On the complexity of a search for a subset of ``similar vectors

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