TY - JOUR
T1 - Approximation algorithm for a quadratic euclidean problem of searching a subset with the largest cardinality
AU - Ageev, Alexander A.
AU - Kel'Manov, Alexander V.
AU - Pyatkin, Artem V.
AU - Khamidullin, Sergey A.
AU - Shenmaier, Vladimir V.
PY - 2017/1/1
Y1 - 2017/1/1
N2 - We consider the problem of searching a subset in a finite set of points of Euclidean space. The problem is to find a cluster (subset) of the largest cardinality satisfying a given upper bound on the sum of squared distances between the cluster elements and their centroid. We prove that this problem is strongly NP-hard and present a polynomial-time 1/2-approximation algorithm.
AB - We consider the problem of searching a subset in a finite set of points of Euclidean space. The problem is to find a cluster (subset) of the largest cardinality satisfying a given upper bound on the sum of squared distances between the cluster elements and their centroid. We prove that this problem is strongly NP-hard and present a polynomial-time 1/2-approximation algorithm.
UR - http://www.scopus.com/inward/record.url?scp=85036605297&partnerID=8YFLogxK
M3 - Conference article
AN - SCOPUS:85036605297
VL - 1987
SP - 19
EP - 23
JO - CEUR Workshop Proceedings
JF - CEUR Workshop Proceedings
SN - 1613-0073
ER -