Standard

Exact pseudopolynomial algorithms for a balanced 2-clustering problem. / Kel’manov, A. V.; Motkova, A. V.

In: Journal of Applied and Industrial Mathematics, Vol. 10, No. 3, 01.07.2016, p. 349-355.

Research output: Contribution to journal › Article › peer-review

Harvard

Kel’manov, AV & Motkova, AV 2016, 'Exact pseudopolynomial algorithms for a balanced 2-clustering problem', Journal of Applied and Industrial Mathematics, vol. 10, no. 3, pp. 349-355. https://doi.org/10.1134/S1990478916030054

APA

Kel’manov, A. V., & Motkova, A. V. (2016). Exact pseudopolynomial algorithms for a balanced 2-clustering problem. Journal of Applied and Industrial Mathematics, 10(3), 349-355. https://doi.org/10.1134/S1990478916030054

Vancouver

Kel’manov AV, Motkova AV. Exact pseudopolynomial algorithms for a balanced 2-clustering problem. Journal of Applied and Industrial Mathematics. 2016 Jul 1;10(3):349-355. doi: 10.1134/S1990478916030054

Author

Kel’manov, A. V. ; Motkova, A. V. / Exact pseudopolynomial algorithms for a balanced 2-clustering problem. In: Journal of Applied and Industrial Mathematics. 2016 ; Vol. 10, No. 3. pp. 349-355.

BibTeX

@article{1b6c57e60d71464f956af3d38ca126d7,
title = "Exact pseudopolynomial algorithms for a balanced 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 sum of the squared intracluster distances from the elements of the clusters to their centers. The weights of sums are the sizes of the clusters. The center of one cluster 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 (as the geometric center). Two variants of the problems are analyzed in which the cluster sizes are either given or unknown. We present and prove some exact pseudopolynomial algorithms in the case of integer components of the input points and fixed space dimension.",
keywords = "balanced clustering, Euclidean space, exact pseudopolynomial algorithm, fixed space dimension, integer inputs, NP-hardness",
author = "Kel{\textquoteright}manov, {A. V.} and Motkova, {A. V.}",
year = "2016",
month = jul,
day = "1",
doi = "10.1134/S1990478916030054",
language = "English",
volume = "10",
pages = "349--355",
journal = "Journal of Applied and Industrial Mathematics",
issn = "1990-4789",
publisher = "Maik Nauka-Interperiodica Publishing",
number = "3",

}

RIS

TY - JOUR

T1 - Exact pseudopolynomial algorithms for a balanced 2-clustering problem

AU - Kel’manov, A. V.

AU - Motkova, A. V.

PY - 2016/7/1

Y1 - 2016/7/1

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 sum of the squared intracluster distances from the elements of the clusters to their centers. The weights of sums are the sizes of the clusters. The center of one cluster 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 (as the geometric center). Two variants of the problems are analyzed in which the cluster sizes are either given or unknown. We present and prove some exact pseudopolynomial algorithms in the case of integer components of the input points and fixed space dimension.

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 sum of the squared intracluster distances from the elements of the clusters to their centers. The weights of sums are the sizes of the clusters. The center of one cluster 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 (as the geometric center). Two variants of the problems are analyzed in which the cluster sizes are either given or unknown. We present and prove some exact pseudopolynomial algorithms in the case of integer components of the input points and fixed space dimension.

KW - balanced clustering

KW - Euclidean space

KW - exact pseudopolynomial algorithm

KW - fixed space dimension

KW - integer inputs

KW - NP-hardness

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

U2 - 10.1134/S1990478916030054

DO - 10.1134/S1990478916030054

M3 - Article

AN - SCOPUS:84983502949

VL - 10

SP - 349

EP - 355

JO - Journal of Applied and Industrial Mathematics

JF - Journal of Applied and Industrial Mathematics

SN - 1990-4789

IS - 3

ER -

ID: 25548217