Standard
An approximation scheme for a weighted two-cluster partition problem. / Kel’manov, Alexander; Motkova, Anna; Shenmaier, Vladimir.
Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers. ed. / WMP VanDerAalst; DI Ignatov; M Khachay; SO Kuznetsov; Lempitsky; IA Lomazova; N Loukachevitch; A Napoli; A Panchenko; PM Pardalos; AV Savchenko; S Wasserman. Springer-Verlag GmbH and Co. KG, 2018. p. 323-333 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10716 LNCS).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Harvard
Kel’manov, A
, Motkova, A & Shenmaier, V 2018,
An approximation scheme for a weighted two-cluster partition problem. in WMP VanDerAalst, DI Ignatov, M Khachay, SO Kuznetsov, Lempitsky, IA Lomazova, N Loukachevitch, A Napoli, A Panchenko, PM Pardalos, AV Savchenko & S Wasserman (eds),
Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10716 LNCS, Springer-Verlag GmbH and Co. KG, pp. 323-333, 6th International Conference on Analysis of Images, Social Networks and Texts, AIST 2017, Moscow, Russian Federation,
27.07.2017.
https://doi.org/10.1007/978-3-319-73013-4_30APA
Kel’manov, A.
, Motkova, A., & Shenmaier, V. (2018).
An approximation scheme for a weighted two-cluster partition problem. In WMP. VanDerAalst, DI. Ignatov, M. Khachay, SO. Kuznetsov, Lempitsky, IA. Lomazova, N. Loukachevitch, A. Napoli, A. Panchenko, PM. Pardalos, AV. Savchenko, & S. Wasserman (Eds.),
Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers (pp. 323-333). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10716 LNCS). Springer-Verlag GmbH and Co. KG.
https://doi.org/10.1007/978-3-319-73013-4_30Vancouver
Kel’manov A
, Motkova A, Shenmaier V.
An approximation scheme for a weighted two-cluster partition problem. In VanDerAalst WMP, Ignatov DI, Khachay M, Kuznetsov SO, Lempitsky, Lomazova IA, Loukachevitch N, Napoli A, Panchenko A, Pardalos PM, Savchenko AV, Wasserman S, editors, Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers. Springer-Verlag GmbH and Co. KG. 2018. p. 323-333. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-73013-4_30
Author
Kel’manov, Alexander
; Motkova, Anna ; Shenmaier, Vladimir. /
An approximation scheme for a weighted two-cluster partition problem. Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers. editor / WMP VanDerAalst ; DI Ignatov ; M Khachay ; SO Kuznetsov ; Lempitsky ; IA Lomazova ; N Loukachevitch ; A Napoli ; A Panchenko ; PM Pardalos ; AV Savchenko ; S Wasserman. Springer-Verlag GmbH and Co. KG, 2018. pp. 323-333 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
BibTeX
@inproceedings{a4043a7f7fd74af097710355ff6c3c93,
title = "An approximation scheme for a weighted two-cluster partition problem",
abstract = "We consider the problem of partitioning a set of Euclidean points into two clusters to minimize the weighted sum of the squared intracluster distances from the elements of the clusters to their centers. The center of one of the clusters is unknown and determined as the average value over all points in the cluster, while the center of the other cluster is the origin. The weight factors for both intracluster sums are given as input. We present an approximation algorithm for the problem, which is based on an adaptive-grid-approach. The algorithm implements a fully polynomial-time approximation scheme (FPTAS) in the case of the fixed space dimension. In the case when the dimension of space is not fixed but is bounded by a slowly growing function of the number of input points, the algorithm realizes a polynomial-time approximation scheme (PTAS).",
keywords = "Euclidean space, FPTAS, NP-hardness, PTAS, Weighted 2-clustering, Euclidean space FPTAS, SET, COMPLEXITY, VECTORS, CLUSTER-ANALYSIS",
author = "Alexander Kel{\textquoteright}manov and Anna Motkova and Vladimir Shenmaier",
note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG 2018.; 6th International Conference on Analysis of Images, Social Networks and Texts, AIST 2017 ; Conference date: 27-07-2017 Through 29-07-2017",
year = "2018",
month = jan,
day = "1",
doi = "10.1007/978-3-319-73013-4_30",
language = "English",
isbn = "9783319730127",
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 = "323--333",
editor = "WMP VanDerAalst and DI Ignatov and M Khachay and SO Kuznetsov and Lempitsky and IA Lomazova and N Loukachevitch and A Napoli and A Panchenko and PM Pardalos and AV Savchenko and S Wasserman",
booktitle = "Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers",
address = "Germany",
}
RIS
TY - GEN
T1 - An approximation scheme for a weighted two-cluster partition problem
AU - Kel’manov, Alexander
AU - Motkova, Anna
AU - Shenmaier, Vladimir
N1 - Publisher Copyright:
© Springer International Publishing AG 2018.
PY - 2018/1/1
Y1 - 2018/1/1
N2 - We consider the problem of partitioning a set of Euclidean points into two clusters to minimize the weighted sum of the squared intracluster distances from the elements of the clusters to their centers. The center of one of the clusters is unknown and determined as the average value over all points in the cluster, while the center of the other cluster is the origin. The weight factors for both intracluster sums are given as input. We present an approximation algorithm for the problem, which is based on an adaptive-grid-approach. The algorithm implements a fully polynomial-time approximation scheme (FPTAS) in the case of the fixed space dimension. In the case when the dimension of space is not fixed but is bounded by a slowly growing function of the number of input points, the algorithm realizes a polynomial-time approximation scheme (PTAS).
AB - We consider the problem of partitioning a set of Euclidean points into two clusters to minimize the weighted sum of the squared intracluster distances from the elements of the clusters to their centers. The center of one of the clusters is unknown and determined as the average value over all points in the cluster, while the center of the other cluster is the origin. The weight factors for both intracluster sums are given as input. We present an approximation algorithm for the problem, which is based on an adaptive-grid-approach. The algorithm implements a fully polynomial-time approximation scheme (FPTAS) in the case of the fixed space dimension. In the case when the dimension of space is not fixed but is bounded by a slowly growing function of the number of input points, the algorithm realizes a polynomial-time approximation scheme (PTAS).
KW - Euclidean space
KW - FPTAS
KW - NP-hardness
KW - PTAS
KW - Weighted 2-clustering
KW - Euclidean space FPTAS
KW - SET
KW - COMPLEXITY
KW - VECTORS
KW - CLUSTER-ANALYSIS
UR - http://www.scopus.com/inward/record.url?scp=85039419654&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-73013-4_30
DO - 10.1007/978-3-319-73013-4_30
M3 - Conference contribution
AN - SCOPUS:85039419654
SN - 9783319730127
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 323
EP - 333
BT - Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers
A2 - VanDerAalst, WMP
A2 - Ignatov, DI
A2 - Khachay, M
A2 - Kuznetsov, SO
A2 - Lempitsky, null
A2 - Lomazova, IA
A2 - Loukachevitch, N
A2 - Napoli, A
A2 - Panchenko, A
A2 - Pardalos, PM
A2 - Savchenko, AV
A2 - Wasserman, S
PB - Springer-Verlag GmbH and Co. KG
T2 - 6th International Conference on Analysis of Images, Social Networks and Texts, AIST 2017
Y2 - 27 July 2017 through 29 July 2017
ER -
