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

Research output: Contribution to journalConference articlepeer-review

Abstract

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.

Original languageEnglish
Pages (from-to)19-23
Number of pages5
JournalCEUR Workshop Proceedings
Volume1987
Publication statusPublished - 1 Jan 2017

Fingerprint

Dive into the research topics of 'Approximation algorithm for a quadratic euclidean problem of searching a subset with the largest cardinality'. Together they form a unique fingerprint.

Cite this