Standard

Approximation algorithm for a quadratic euclidean problem of searching a subset with the largest cardinality. / Ageev, Alexander A.; Kel'Manov, Alexander V.; Pyatkin, Artem V. и др.

в: CEUR Workshop Proceedings, Том 1987, 01.01.2017, стр. 19-23.

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

Harvard

Ageev, AA, Kel'Manov, AV, Pyatkin, AV, Khamidullin, SA & Shenmaier, VV 2017, 'Approximation algorithm for a quadratic euclidean problem of searching a subset with the largest cardinality', CEUR Workshop Proceedings, Том. 1987, стр. 19-23.

APA

Ageev, A. A., Kel'Manov, A. V., Pyatkin, A. V., Khamidullin, S. A., & Shenmaier, V. V. (2017). Approximation algorithm for a quadratic euclidean problem of searching a subset with the largest cardinality. CEUR Workshop Proceedings, 1987, 19-23.

Vancouver

Ageev AA, Kel'Manov AV, Pyatkin AV, Khamidullin SA, Shenmaier VV. Approximation algorithm for a quadratic euclidean problem of searching a subset with the largest cardinality. CEUR Workshop Proceedings. 2017 янв. 1;1987:19-23.

Author

Ageev, Alexander A. ; Kel'Manov, Alexander V. ; Pyatkin, Artem V. и др. / Approximation algorithm for a quadratic euclidean problem of searching a subset with the largest cardinality. в: CEUR Workshop Proceedings. 2017 ; Том 1987. стр. 19-23.

BibTeX

@article{097b4cb1e91d482aa5786cc247b75cb8,
title = "Approximation algorithm for a quadratic euclidean problem of searching a subset with the largest cardinality",
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.",
author = "Ageev, {Alexander A.} and Kel'Manov, {Alexander V.} and Pyatkin, {Artem V.} and Khamidullin, {Sergey A.} and Shenmaier, {Vladimir V.}",
year = "2017",
month = jan,
day = "1",
language = "English",
volume = "1987",
pages = "19--23",
journal = "CEUR Workshop Proceedings",
issn = "1613-0073",
publisher = "CEUR-WS",

}

RIS

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 -

ID: 10066118