Standard

Polynomial-Time Approximation Algorithm for the Problem of Cardinality-Weighted Variance-Based 2-Clustering with a Given Center. / Kel’manov, A. V.; Motkova, A. V.

в: Computational Mathematics and Mathematical Physics, Том 58, № 1, 01.01.2018, стр. 130-136.

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

Harvard

Kel’manov, AV & Motkova, AV 2018, 'Polynomial-Time Approximation Algorithm for the Problem of Cardinality-Weighted Variance-Based 2-Clustering with a Given Center', Computational Mathematics and Mathematical Physics, Том. 58, № 1, стр. 130-136. https://doi.org/10.1134/S0965542518010074

APA

Kel’manov, A. V., & Motkova, A. V. (2018). Polynomial-Time Approximation Algorithm for the Problem of Cardinality-Weighted Variance-Based 2-Clustering with a Given Center. Computational Mathematics and Mathematical Physics, 58(1), 130-136. https://doi.org/10.1134/S0965542518010074

Vancouver

Kel’manov AV, Motkova AV. Polynomial-Time Approximation Algorithm for the Problem of Cardinality-Weighted Variance-Based 2-Clustering with a Given Center. Computational Mathematics and Mathematical Physics. 2018 янв. 1;58(1):130-136. doi: 10.1134/S0965542518010074

Author

Kel’manov, A. V. ; Motkova, A. V. / Polynomial-Time Approximation Algorithm for the Problem of Cardinality-Weighted Variance-Based 2-Clustering with a Given Center. в: Computational Mathematics and Mathematical Physics. 2018 ; Том 58, № 1. стр. 130-136.

BibTeX

@article{59f0a6792b654551a1649f4748489665,
title = "Polynomial-Time Approximation Algorithm for the Problem of Cardinality-Weighted Variance-Based 2-Clustering with a Given Center",
abstract = "A strongly NP-hard problem of partitioning a finite set of points of Euclidean space into two clusters is considered. The solution criterion is the minimum of the sum (over both clusters) of weighted sums of squared distances from the elements of each cluster to its geometric center. The weights of the sums are equal to the cardinalities of the desired clusters. The center of one cluster is given as input, while the center of the other is unknown and is determined as the point of space equal to the mean of the cluster elements. A version of the problem is analyzed in which the cardinalities of the clusters are given as input. A polynomial-time 2-approximation algorithm for solving the problem is constructed.",
keywords = "Euclidean space, NP-hardness, polynomial-time 2-approximation algorithm, weighted 2-clustering",
author = "Kel{\textquoteright}manov, {A. V.} and Motkova, {A. V.}",
year = "2018",
month = jan,
day = "1",
doi = "10.1134/S0965542518010074",
language = "English",
volume = "58",
pages = "130--136",
journal = "Computational Mathematics and Mathematical Physics",
issn = "0965-5425",
publisher = "PLEIADES PUBLISHING INC",
number = "1",

}

RIS

TY - JOUR

T1 - Polynomial-Time Approximation Algorithm for the Problem of Cardinality-Weighted Variance-Based 2-Clustering with a Given Center

AU - Kel’manov, A. V.

AU - Motkova, A. V.

PY - 2018/1/1

Y1 - 2018/1/1

N2 - A strongly NP-hard problem of partitioning a finite set of points of Euclidean space into two clusters is considered. The solution criterion is the minimum of the sum (over both clusters) of weighted sums of squared distances from the elements of each cluster to its geometric center. The weights of the sums are equal to the cardinalities of the desired clusters. The center of one cluster is given as input, while the center of the other is unknown and is determined as the point of space equal to the mean of the cluster elements. A version of the problem is analyzed in which the cardinalities of the clusters are given as input. A polynomial-time 2-approximation algorithm for solving the problem is constructed.

AB - A strongly NP-hard problem of partitioning a finite set of points of Euclidean space into two clusters is considered. The solution criterion is the minimum of the sum (over both clusters) of weighted sums of squared distances from the elements of each cluster to its geometric center. The weights of the sums are equal to the cardinalities of the desired clusters. The center of one cluster is given as input, while the center of the other is unknown and is determined as the point of space equal to the mean of the cluster elements. A version of the problem is analyzed in which the cardinalities of the clusters are given as input. A polynomial-time 2-approximation algorithm for solving the problem is constructed.

KW - Euclidean space

KW - NP-hardness

KW - polynomial-time 2-approximation algorithm

KW - weighted 2-clustering

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

U2 - 10.1134/S0965542518010074

DO - 10.1134/S0965542518010074

M3 - Article

AN - SCOPUS:85042701688

VL - 58

SP - 130

EP - 136

JO - Computational Mathematics and Mathematical Physics

JF - Computational Mathematics and Mathematical Physics

SN - 0965-5425

IS - 1

ER -

ID: 10496999