Approximation Algorithm for a Quadratic Euclidean Problem of Searching a Subset with the Largest Cardinality

Approximation Algorithm for a Quadratic Euclidean Problem of Searching a Subset with the Largest Cardinality Full article

Journal

CEUR Workshop Proceedings
ISSN: 1613-0073

Output data

Year: 2017, Volume: 1987, Pages: 19-23 Pages count : 5

Authors

Ageev Alexander A. ¹ , Kelmanov Alexander V. ^1,2 , Khamidullin Serrgey A. ¹ , Pyatkin Artem ^1,2 , Shenmaier V. V. ¹

Affiliations

1	Sobolev Institute of Mathematics
2	Novosibirsk State University

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.

Ageev A.A. , Kelmanov A.V. , Khamidullin S.A. , Pyatkin A. , Shenmaier V.V.
Approximation Algorithm for a Quadratic Euclidean Problem of Searching a Subset with the Largest Cardinality
CEUR Workshop Proceedings. 2017. V.1987. P.19-23. Scopus

Scopus:

2-s2.0-85036605297

Пока нет цитирований