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 -