Standard
Fast and exact algorithms for some NP-hard 2-clustering problems in the one-dimensional case. / Kel’manov, Alexander; Khandeev, Vladimir.
Analysis of Images, Social Networks and Texts - 8th International Conference, AIST 2019, Revised Selected Papers. ed. / Wil M.P. van der Aalst; Vladimir Batagelj; Dmitry I. Ignatov; Valentina Kuskova; Sergei O. Kuznetsov; Irina A. Lomazova; Michael Khachay; Andrey Kutuzov; Natalia Loukachevitch; Amedeo Napoli; Panos M. Pardalos; Marcello Pelillo; Andrey V. Savchenko; Elena Tutubalina. Springer International Publishing AG, 2019. p. 377-387 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11832 LNCS).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Harvard
Kel’manov, A
& Khandeev, V 2019,
Fast and exact algorithms for some NP-hard 2-clustering problems in the one-dimensional case. in WMP van der Aalst, V Batagelj, DI Ignatov, V Kuskova, SO Kuznetsov, IA Lomazova, M Khachay, A Kutuzov, N Loukachevitch, A Napoli, PM Pardalos, M Pelillo, AV Savchenko & E Tutubalina (eds),
Analysis of Images, Social Networks and Texts - 8th International Conference, AIST 2019, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11832 LNCS, Springer International Publishing AG, pp. 377-387, 8th International Conference on Analysis of Images, Social Networks and Texts, AIST 2019, Kazan, Russian Federation,
17.07.2019.
https://doi.org/10.1007/978-3-030-37334-4_34APA
Kel’manov, A.
, & Khandeev, V. (2019).
Fast and exact algorithms for some NP-hard 2-clustering problems in the one-dimensional case. In W. M. P. van der Aalst, V. Batagelj, D. I. Ignatov, V. Kuskova, S. O. Kuznetsov, I. A. Lomazova, M. Khachay, A. Kutuzov, N. Loukachevitch, A. Napoli, P. M. Pardalos, M. Pelillo, A. V. Savchenko, & E. Tutubalina (Eds.),
Analysis of Images, Social Networks and Texts - 8th International Conference, AIST 2019, Revised Selected Papers (pp. 377-387). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11832 LNCS). Springer International Publishing AG.
https://doi.org/10.1007/978-3-030-37334-4_34Vancouver
Kel’manov A
, Khandeev V.
Fast and exact algorithms for some NP-hard 2-clustering problems in the one-dimensional case. In van der Aalst WMP, Batagelj V, Ignatov DI, Kuskova V, Kuznetsov SO, Lomazova IA, Khachay M, Kutuzov A, Loukachevitch N, Napoli A, Pardalos PM, Pelillo M, Savchenko AV, Tutubalina E, editors, Analysis of Images, Social Networks and Texts - 8th International Conference, AIST 2019, Revised Selected Papers. Springer International Publishing AG. 2019. p. 377-387. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-37334-4_34
Author
Kel’manov, Alexander
; Khandeev, Vladimir. /
Fast and exact algorithms for some NP-hard 2-clustering problems in the one-dimensional case. Analysis of Images, Social Networks and Texts - 8th International Conference, AIST 2019, Revised Selected Papers. editor / Wil M.P. van der Aalst ; Vladimir Batagelj ; Dmitry I. Ignatov ; Valentina Kuskova ; Sergei O. Kuznetsov ; Irina A. Lomazova ; Michael Khachay ; Andrey Kutuzov ; Natalia Loukachevitch ; Amedeo Napoli ; Panos M. Pardalos ; Marcello Pelillo ; Andrey V. Savchenko ; Elena Tutubalina. Springer International Publishing AG, 2019. pp. 377-387 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
BibTeX
@inproceedings{d76bf9f812e14fd199e7b9f8e8c1401a,
title = "Fast and exact algorithms for some NP-hard 2-clustering problems in the one-dimensional case",
abstract = "We consider several well-known optimization 2-clustering (2-partitioning) problems of a finite set of points in Euclidean space. All clustering problems considered are induced by applied problems in Data analysis, Data cleaning, and Data mining. In the general case, all these optimization problems are strongly NP-hard. In the paper, we present a brief overview of the results on the problems computational complexity and on their solvability in the one-dimensional case. We present and propose well-known and new, simple and fast exact algorithms with O(N log N) and O(N) running times for the one-dimensional case of these problems.",
keywords = "2-clustering, 2-partitioning, Euclidean space, Fast exact algorithms, NP-hardness, Polynomial-time solvability in the 1D case",
author = "Alexander Kel{\textquoteright}manov and Vladimir Khandeev",
note = "Publisher Copyright: {\textcopyright} Springer Nature Switzerland AG 2019. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.; 8th International Conference on Analysis of Images, Social Networks and Texts, AIST 2019 ; Conference date: 17-07-2019 Through 19-07-2019",
year = "2019",
month = jan,
day = "1",
doi = "10.1007/978-3-030-37334-4_34",
language = "English",
isbn = "9783030373337",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer International Publishing AG",
pages = "377--387",
editor = "{van der Aalst}, {Wil M.P.} and Vladimir Batagelj and Ignatov, {Dmitry I.} and Valentina Kuskova and Kuznetsov, {Sergei O.} and Lomazova, {Irina A.} and Michael Khachay and Andrey Kutuzov and Natalia Loukachevitch and Amedeo Napoli and Pardalos, {Panos M.} and Marcello Pelillo and Savchenko, {Andrey V.} and Elena Tutubalina",
booktitle = "Analysis of Images, Social Networks and Texts - 8th International Conference, AIST 2019, Revised Selected Papers",
address = "Switzerland",
}
RIS
TY - GEN
T1 - Fast and exact algorithms for some NP-hard 2-clustering problems in the one-dimensional case
AU - Kel’manov, Alexander
AU - Khandeev, Vladimir
N1 - Publisher Copyright:
© Springer Nature Switzerland AG 2019.
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
PY - 2019/1/1
Y1 - 2019/1/1
N2 - We consider several well-known optimization 2-clustering (2-partitioning) problems of a finite set of points in Euclidean space. All clustering problems considered are induced by applied problems in Data analysis, Data cleaning, and Data mining. In the general case, all these optimization problems are strongly NP-hard. In the paper, we present a brief overview of the results on the problems computational complexity and on their solvability in the one-dimensional case. We present and propose well-known and new, simple and fast exact algorithms with O(N log N) and O(N) running times for the one-dimensional case of these problems.
AB - We consider several well-known optimization 2-clustering (2-partitioning) problems of a finite set of points in Euclidean space. All clustering problems considered are induced by applied problems in Data analysis, Data cleaning, and Data mining. In the general case, all these optimization problems are strongly NP-hard. In the paper, we present a brief overview of the results on the problems computational complexity and on their solvability in the one-dimensional case. We present and propose well-known and new, simple and fast exact algorithms with O(N log N) and O(N) running times for the one-dimensional case of these problems.
KW - 2-clustering
KW - 2-partitioning
KW - Euclidean space
KW - Fast exact algorithms
KW - NP-hardness
KW - Polynomial-time solvability in the 1D case
UR - http://www.scopus.com/inward/record.url?scp=85077501196&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-37334-4_34
DO - 10.1007/978-3-030-37334-4_34
M3 - Conference contribution
AN - SCOPUS:85077501196
SN - 9783030373337
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 377
EP - 387
BT - Analysis of Images, Social Networks and Texts - 8th International Conference, AIST 2019, Revised Selected Papers
A2 - van der Aalst, Wil M.P.
A2 - Batagelj, Vladimir
A2 - Ignatov, Dmitry I.
A2 - Kuskova, Valentina
A2 - Kuznetsov, Sergei O.
A2 - Lomazova, Irina A.
A2 - Khachay, Michael
A2 - Kutuzov, Andrey
A2 - Loukachevitch, Natalia
A2 - Napoli, Amedeo
A2 - Pardalos, Panos M.
A2 - Pelillo, Marcello
A2 - Savchenko, Andrey V.
A2 - Tutubalina, Elena
PB - Springer International Publishing AG
T2 - 8th International Conference on Analysis of Images, Social Networks and Texts, AIST 2019
Y2 - 17 July 2019 through 19 July 2019
ER -
