On the complexity of a search for a subset of ``similar vectors
From MaRDI portal
Publication:542229
DOI10.1134/S1064562408040273zbMath1217.90142OpenAlexW1990400773MaRDI QIDQ542229
Artem V. Pyatkin, Alexander Kel'Manov
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
Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)
Related Items (17)
Exact algorithms of searching for the largest size cluster in two integer 2-clustering problems ⋮ 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 ⋮ Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters ⋮ PTAS for \(p\)-means \(q\)-medoids \(r\)-given clustering problem ⋮ NP-hardness of some quadratic Euclidean 2-clustering problems ⋮ NP-hardness of the Euclidean Max-Cut problem ⋮ An approximation polynomial-time algorithm for a sequence bi-clustering problem ⋮ On the complexity and approximability of some Euclidean optimal summing problems ⋮ 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 ⋮ Easy NP-hardness Proofs of Some Subset Choice Problems ⋮ The Problem K-Means and Given J-Centers: Polynomial Solvability in One Dimension ⋮ Complexity of the weighted max-cut in Euclidean space ⋮ A randomized algorithm for two-cluster partition of a set of vectors
Cites Work
This page was built for publication: On the complexity of a search for a subset of ``similar vectors
