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

Alexander Kel'Manov; Anna Motkova

doi:10.1109/SIBIRCON.2017.8109845

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

Alexander Kel'Manov, Anna Motkova

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › рецензирование

Аннотация

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.

Язык оригинала	английский
Название основной публикации	Proceedings - 2017 International Multi-Conference on Engineering, Computer and Information Sciences, SIBIRCON 2017
Издатель	Institute of Electrical and Electronics Engineers Inc.
Страницы	94-96
Число страниц	3
ISBN (электронное издание)	9781538615966
DOI	https://doi.org/10.1109/SIBIRCON.2017.8109845
Состояние	Опубликовано - 14 ноя 2017
Событие	2017 International Multi-Conference on Engineering, Computer and Information Sciences, SIBIRCON 2017 - Novosibirsk, Российская Федерация Продолжительность: 18 сен 2017 → 22 сен 2017

Конференция

Конференция	2017 International Multi-Conference on Engineering, Computer and Information Sciences, SIBIRCON 2017
Страна	Российская Федерация
Город	Novosibirsk
Период	18.09.2017 → 22.09.2017

Доступ к документу

10.1109/SIBIRCON.2017.8109845

Link to publication in Scopus

Fingerprint

Подробные сведения о темах исследования «An approximation polynomial-time algorithm for a cardinality-weighted 2-clustering problem». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать

Kel'Manov, A., & Motkova, A. (2017). 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 (стр. 94-96). [8109845] Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/SIBIRCON.2017.8109845

@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",

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",

note = "2017 International Multi-Conference on Engineering, Computer and Information Sciences, SIBIRCON 2017 ; Conference date: 18-09-2017 Through 22-09-2017",

}

Kel'Manov, A & Motkova, A 2017, 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., 8109845, Institute of Electrical and Electronics Engineers Inc., стр. 94-96, 2017 International Multi-Conference on Engineering, Computer and Information Sciences, SIBIRCON 2017, Novosibirsk, Российская Федерация, 18.09.2017. https://doi.org/10.1109/SIBIRCON.2017.8109845

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. стр. 94-96 8109845.

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › рецензирование

TY - GEN

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

AU - Kel'Manov, Alexander

AU - Motkova, Anna

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 -