Standard

A fully polynomial-time approximation scheme for a special case of a balanced 2-clustering problem. / Kel’manov, Alexander; Motkova, Anna.

Discrete Optimization and Operations Research - 9th International Conference, DOOR 2016, Proceedings. ed. / Michael Khachay; Panos Pardalos; Yury Kochetov; Vladimir Beresnev; Evgeni Nurminski. Springer-Verlag GmbH and Co. KG, 2016. p. 182-192 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9869 LNCS).

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

Harvard

Kel’manov, A & Motkova, A 2016, A fully polynomial-time approximation scheme for a special case of a balanced 2-clustering problem. in M Khachay, P Pardalos, Y Kochetov, V Beresnev & E Nurminski (eds), Discrete Optimization and Operations Research - 9th International Conference, DOOR 2016, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9869 LNCS, Springer-Verlag GmbH and Co. KG, pp. 182-192, 9th International Conference on Discrete Optimization and Operations Research, DOOR 2016, Vladivostok, Russian Federation, 19.09.2016. https://doi.org/10.1007/978-3-319-44914-2_15

APA

Kel’manov, A., & Motkova, A. (2016). A fully polynomial-time approximation scheme for a special case of a balanced 2-clustering problem. In M. Khachay, P. Pardalos, Y. Kochetov, V. Beresnev, & E. Nurminski (Eds.), Discrete Optimization and Operations Research - 9th International Conference, DOOR 2016, Proceedings (pp. 182-192). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9869 LNCS). Springer-Verlag GmbH and Co. KG. https://doi.org/10.1007/978-3-319-44914-2_15

Vancouver

Kel’manov A, Motkova A. A fully polynomial-time approximation scheme for a special case of a balanced 2-clustering problem. In Khachay M, Pardalos P, Kochetov Y, Beresnev V, Nurminski E, editors, Discrete Optimization and Operations Research - 9th International Conference, DOOR 2016, Proceedings. Springer-Verlag GmbH and Co. KG. 2016. p. 182-192. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-44914-2_15

Author

Kel’manov, Alexander ; Motkova, Anna. / A fully polynomial-time approximation scheme for a special case of a balanced 2-clustering problem. Discrete Optimization and Operations Research - 9th International Conference, DOOR 2016, Proceedings. editor / Michael Khachay ; Panos Pardalos ; Yury Kochetov ; Vladimir Beresnev ; Evgeni Nurminski. Springer-Verlag GmbH and Co. KG, 2016. pp. 182-192 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{9bfba5f063ed4bab953da0ba28ac3912,
title = "A fully polynomial-time approximation scheme for a special case of 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 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 geometric center (centroid), i.e. the average value over all points in the cluster. We analyze the variant of the problem with cardinality constraints. We present an approximation algorithm for the problem and prove that it is a fully polynomial-time approximation scheme when the space dimension is bounded by a constant.",
keywords = "Euclidian space, Fixed dimension, FPTAS, NP-hardness",
author = "Alexander Kel{\textquoteright}manov and Anna Motkova",
year = "2016",
doi = "10.1007/978-3-319-44914-2_15",
language = "English",
isbn = "9783319449135",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer-Verlag GmbH and Co. KG",
pages = "182--192",
editor = "Michael Khachay and Panos Pardalos and Yury Kochetov and Vladimir Beresnev and Evgeni Nurminski",
booktitle = "Discrete Optimization and Operations Research - 9th International Conference, DOOR 2016, Proceedings",
address = "Germany",
note = "9th International Conference on Discrete Optimization and Operations Research, DOOR 2016 ; Conference date: 19-09-2016 Through 23-09-2016",

}

RIS

TY - GEN

T1 - A fully polynomial-time approximation scheme for a special case of a balanced 2-clustering problem

AU - Kel’manov, Alexander

AU - Motkova, Anna

PY - 2016

Y1 - 2016

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 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 geometric center (centroid), i.e. the average value over all points in the cluster. We analyze the variant of the problem with cardinality constraints. We present an approximation algorithm for the problem and prove that it is a fully polynomial-time approximation scheme when the space dimension is bounded by a constant.

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 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 geometric center (centroid), i.e. the average value over all points in the cluster. We analyze the variant of the problem with cardinality constraints. We present an approximation algorithm for the problem and prove that it is a fully polynomial-time approximation scheme when the space dimension is bounded by a constant.

KW - Euclidian space

KW - Fixed dimension

KW - FPTAS

KW - NP-hardness

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

U2 - 10.1007/978-3-319-44914-2_15

DO - 10.1007/978-3-319-44914-2_15

M3 - Conference contribution

AN - SCOPUS:84988037221

SN - 9783319449135

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 182

EP - 192

BT - Discrete Optimization and Operations Research - 9th International Conference, DOOR 2016, Proceedings

A2 - Khachay, Michael

A2 - Pardalos, Panos

A2 - Kochetov, Yury

A2 - Beresnev, Vladimir

A2 - Nurminski, Evgeni

PB - Springer-Verlag GmbH and Co. KG

T2 - 9th International Conference on Discrete Optimization and Operations Research, DOOR 2016

Y2 - 19 September 2016 through 23 September 2016

ER -

ID: 25548158