Approximation Algorithm for a Quadratic Euclidean Problem of Searching a Subset with the Largest Cardinality | Sciact - Система учета научной деятельности ИМ СО РАН

Approximation Algorithm for a Quadratic Euclidean Problem of Searching a Subset with the Largest Cardinality Научная публикация

Журнал

CEUR Workshop Proceedings
ISSN: 1613-0073

Вых. Данные

Год: 2017, Том: 1987, Страницы: 19-23 Страниц : 5

Авторы

Ageev Alexander A. ¹ , Kelmanov Alexander V. ^1,2 , Khamidullin Serrgey A. ¹ , Pyatkin Artem ^1,2 , Шенмайер В. В. ¹

Организации

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

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