Standard
Exact Algorithm for One Cardinality-Weighted 2-Partitioning Problem of a Sequence. / Kel’manov, Alexander; Khamidullin, Sergey; Panasenko, Anna.
Learning and Intelligent Optimization - 13th International Conference, LION 13, Revised Selected Papers. ed. / Nikolaos F. Matsatsinis; Yannis Marinakis; Panos Pardalos. Springer Gabler, 2020. p. 135-145 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11968 LNCS).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Harvard
Kel’manov, A, Khamidullin, S
& Panasenko, A 2020,
Exact Algorithm for One Cardinality-Weighted 2-Partitioning Problem of a Sequence. in NF Matsatsinis, Y Marinakis & P Pardalos (eds),
Learning and Intelligent Optimization - 13th International Conference, LION 13, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11968 LNCS, Springer Gabler, pp. 135-145, 13th International Conference on Learning and Intelligent Optimization, LION 13, Chania, Greece,
27.05.2019.
https://doi.org/10.1007/978-3-030-38629-0_11APA
Kel’manov, A., Khamidullin, S.
, & Panasenko, A. (2020).
Exact Algorithm for One Cardinality-Weighted 2-Partitioning Problem of a Sequence. In N. F. Matsatsinis, Y. Marinakis, & P. Pardalos (Eds.),
Learning and Intelligent Optimization - 13th International Conference, LION 13, Revised Selected Papers (pp. 135-145). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11968 LNCS). Springer Gabler.
https://doi.org/10.1007/978-3-030-38629-0_11Vancouver
Kel’manov A, Khamidullin S
, Panasenko A.
Exact Algorithm for One Cardinality-Weighted 2-Partitioning Problem of a Sequence. In Matsatsinis NF, Marinakis Y, Pardalos P, editors, Learning and Intelligent Optimization - 13th International Conference, LION 13, Revised Selected Papers. Springer Gabler. 2020. p. 135-145. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-38629-0_11
Author
Kel’manov, Alexander ; Khamidullin, Sergey
; Panasenko, Anna. /
Exact Algorithm for One Cardinality-Weighted 2-Partitioning Problem of a Sequence. Learning and Intelligent Optimization - 13th International Conference, LION 13, Revised Selected Papers. editor / Nikolaos F. Matsatsinis ; Yannis Marinakis ; Panos Pardalos. Springer Gabler, 2020. pp. 135-145 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
BibTeX
@inproceedings{6eb876b6973147b8b8cb74b9c6f77be0,
title = "Exact Algorithm for One Cardinality-Weighted 2-Partitioning Problem of a Sequence",
abstract = "We consider a problem of 2-partitioning a finite sequence of points in Euclidean space into two clusters of the given sizes with some additional constraints. The solution criterion is the minimum of the sum (over both clusters) of weighted intracluster sums of squared distances between the elements of each cluster and its center. The weights of the intracluster 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 one is unknown and is determined as a geometric center, i.e. as a point of space equal to the mean of the cluster elements. The following constraints hold: the difference between the indices of two subsequent points included in the first cluster is bounded from above and below by given some constants. It is shown that the considered problem is the strongly NP-hard one. An exact algorithm is proposed for the case of integer-valued input of the problem. This algorithm has a pseudopolynomial running time if the space dimension is fixed.",
keywords = "Euclidean space, Exact algorithm, Fixed space dimension, Integer coordinates, NP-hard problem, Pseudopolynomial time, Quadratic variation, Sequence of points, Weighted 2-partition",
author = "Alexander Kel{\textquoteright}manov and Sergey Khamidullin and Anna Panasenko",
note = "Publisher Copyright: {\textcopyright} 2020, Springer Nature Switzerland AG. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.; 13th International Conference on Learning and Intelligent Optimization, LION 13 ; Conference date: 27-05-2019 Through 31-05-2019",
year = "2020",
month = jan,
day = "1",
doi = "10.1007/978-3-030-38629-0_11",
language = "English",
isbn = "9783030386283",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Gabler",
pages = "135--145",
editor = "Matsatsinis, {Nikolaos F.} and Yannis Marinakis and Panos Pardalos",
booktitle = "Learning and Intelligent Optimization - 13th International Conference, LION 13, Revised Selected Papers",
address = "Germany",
}
RIS
TY - GEN
T1 - Exact Algorithm for One Cardinality-Weighted 2-Partitioning Problem of a Sequence
AU - Kel’manov, Alexander
AU - Khamidullin, Sergey
AU - Panasenko, Anna
N1 - Publisher Copyright:
© 2020, Springer Nature Switzerland AG.
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
PY - 2020/1/1
Y1 - 2020/1/1
N2 - We consider a problem of 2-partitioning a finite sequence of points in Euclidean space into two clusters of the given sizes with some additional constraints. The solution criterion is the minimum of the sum (over both clusters) of weighted intracluster sums of squared distances between the elements of each cluster and its center. The weights of the intracluster 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 one is unknown and is determined as a geometric center, i.e. as a point of space equal to the mean of the cluster elements. The following constraints hold: the difference between the indices of two subsequent points included in the first cluster is bounded from above and below by given some constants. It is shown that the considered problem is the strongly NP-hard one. An exact algorithm is proposed for the case of integer-valued input of the problem. This algorithm has a pseudopolynomial running time if the space dimension is fixed.
AB - We consider a problem of 2-partitioning a finite sequence of points in Euclidean space into two clusters of the given sizes with some additional constraints. The solution criterion is the minimum of the sum (over both clusters) of weighted intracluster sums of squared distances between the elements of each cluster and its center. The weights of the intracluster 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 one is unknown and is determined as a geometric center, i.e. as a point of space equal to the mean of the cluster elements. The following constraints hold: the difference between the indices of two subsequent points included in the first cluster is bounded from above and below by given some constants. It is shown that the considered problem is the strongly NP-hard one. An exact algorithm is proposed for the case of integer-valued input of the problem. This algorithm has a pseudopolynomial running time if the space dimension is fixed.
KW - Euclidean space
KW - Exact algorithm
KW - Fixed space dimension
KW - Integer coordinates
KW - NP-hard problem
KW - Pseudopolynomial time
KW - Quadratic variation
KW - Sequence of points
KW - Weighted 2-partition
UR - http://www.scopus.com/inward/record.url?scp=85082400710&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-38629-0_11
DO - 10.1007/978-3-030-38629-0_11
M3 - Conference contribution
AN - SCOPUS:85082400710
SN - 9783030386283
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 135
EP - 145
BT - Learning and Intelligent Optimization - 13th International Conference, LION 13, Revised Selected Papers
A2 - Matsatsinis, Nikolaos F.
A2 - Marinakis, Yannis
A2 - Pardalos, Panos
PB - Springer Gabler
T2 - 13th International Conference on Learning and Intelligent Optimization, LION 13
Y2 - 27 May 2019 through 31 May 2019
ER -
