Approximation algorithm for a quadratic euclidean problem of searching a subset with the largest cardinality

Alexander A. Ageev, Alexander V. Kel'Manov, Artem V. Pyatkin, Sergey A. Khamidullin, Vladimir V. Shenmaier

Результат исследования: Научные публикации в периодических изданияхстатья по материалам конференции

Аннотация

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.

Язык оригиналаанглийский
Страницы (с-по)19-23
Число страниц5
ЖурналCEUR Workshop Proceedings
Том1987
СостояниеОпубликовано - 1 янв 2017

Fingerprint Подробные сведения о темах исследования «Approximation algorithm for a quadratic euclidean problem of searching a subset with the largest cardinality». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать