Standard

An approximation polynomial-time algorithm for a cardinality-weighted 2-clustering problem. / Kel'Manov, Alexander; Motkova, Anna.

Proceedings - 2017 International Multi-Conference on Engineering, Computer and Information Sciences, SIBIRCON 2017. Institute of Electrical and Electronics Engineers Inc., 2017. p. 94-96 8109845.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

Kel'Manov, A & Motkova, A 2017, An approximation polynomial-time algorithm for a cardinality-weighted 2-clustering problem. in Proceedings - 2017 International Multi-Conference on Engineering, Computer and Information Sciences, SIBIRCON 2017., 8109845, Institute of Electrical and Electronics Engineers Inc., pp. 94-96, 2017 International Multi-Conference on Engineering, Computer and Information Sciences, SIBIRCON 2017, Novosibirsk, Russian Federation, 18.09.2017. https://doi.org/10.1109/SIBIRCON.2017.8109845

APA

Kel'Manov, A., & Motkova, A. (2017). An approximation polynomial-time algorithm for a cardinality-weighted 2-clustering problem. In Proceedings - 2017 International Multi-Conference on Engineering, Computer and Information Sciences, SIBIRCON 2017 (pp. 94-96). [8109845] Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/SIBIRCON.2017.8109845

Vancouver

Kel'Manov A, Motkova A. An approximation polynomial-time algorithm for a cardinality-weighted 2-clustering problem. In Proceedings - 2017 International Multi-Conference on Engineering, Computer and Information Sciences, SIBIRCON 2017. Institute of Electrical and Electronics Engineers Inc. 2017. p. 94-96. 8109845 doi: 10.1109/SIBIRCON.2017.8109845

Author

Kel'Manov, Alexander ; Motkova, Anna. / An approximation polynomial-time algorithm for a cardinality-weighted 2-clustering problem. Proceedings - 2017 International Multi-Conference on Engineering, Computer and Information Sciences, SIBIRCON 2017. Institute of Electrical and Electronics Engineers Inc., 2017. pp. 94-96

BibTeX

@inproceedings{166cdb3ba83444008e80d451e18e252f,
title = "An approximation polynomial-time algorithm for a cardinality-weighted 2-clustering problem",
abstract = "We consider the strongly NP-hard problem of partitioning a set of Euclidean points into two clusters so as to minimize the sum over both clusters of the weighted sums of the squared intracluster distances from the elements of the clusters to their centers. The weights of sums are the cardinalities of the clusters. The center of one of the clusters is given as input, while the center of the other cluster is unknown and determined as the average value over all points in the cluster. The variant of the problem in which the cardinalities of the clusters are parts of the input is analyzed. We present and prove a 2-approximation polynomial-time algorithm for this problem.",
keywords = "2-approximation polynomial-time algorithm, Euclidean space, NP-hardness, Weighted-clustering",
author = "Alexander Kel'Manov and Anna Motkova",
note = "Publisher Copyright: {\textcopyright} 2017 IEEE.; 2017 International Multi-Conference on Engineering, Computer and Information Sciences, SIBIRCON 2017 ; Conference date: 18-09-2017 Through 22-09-2017",
year = "2017",
month = nov,
day = "14",
doi = "10.1109/SIBIRCON.2017.8109845",
language = "English",
pages = "94--96",
booktitle = "Proceedings - 2017 International Multi-Conference on Engineering, Computer and Information Sciences, SIBIRCON 2017",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
address = "United States",

}

RIS

TY - GEN

T1 - An approximation polynomial-time algorithm for a cardinality-weighted 2-clustering problem

AU - Kel'Manov, Alexander

AU - Motkova, Anna

N1 - Publisher Copyright: © 2017 IEEE.

PY - 2017/11/14

Y1 - 2017/11/14

N2 - We consider the strongly NP-hard problem of partitioning a set of Euclidean points into two clusters so as to minimize the sum over both clusters of the weighted sums of the squared intracluster distances from the elements of the clusters to their centers. The weights of sums are the cardinalities of the clusters. The center of one of the clusters is given as input, while the center of the other cluster is unknown and determined as the average value over all points in the cluster. The variant of the problem in which the cardinalities of the clusters are parts of the input is analyzed. We present and prove a 2-approximation polynomial-time algorithm for this problem.

AB - We consider the strongly NP-hard problem of partitioning a set of Euclidean points into two clusters so as to minimize the sum over both clusters of the weighted sums of the squared intracluster distances from the elements of the clusters to their centers. The weights of sums are the cardinalities of the clusters. The center of one of the clusters is given as input, while the center of the other cluster is unknown and determined as the average value over all points in the cluster. The variant of the problem in which the cardinalities of the clusters are parts of the input is analyzed. We present and prove a 2-approximation polynomial-time algorithm for this problem.

KW - 2-approximation polynomial-time algorithm

KW - Euclidean space

KW - NP-hardness

KW - Weighted-clustering

UR - http://www.scopus.com/inward/record.url?scp=85040516700&partnerID=8YFLogxK

U2 - 10.1109/SIBIRCON.2017.8109845

DO - 10.1109/SIBIRCON.2017.8109845

M3 - Conference contribution

AN - SCOPUS:85040516700

SP - 94

EP - 96

BT - Proceedings - 2017 International Multi-Conference on Engineering, Computer and Information Sciences, SIBIRCON 2017

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2017 International Multi-Conference on Engineering, Computer and Information Sciences, SIBIRCON 2017

Y2 - 18 September 2017 through 22 September 2017

ER -

ID: 9115195