Exact Algorithm for the One-Dimensional Quadratic Euclidean Cardinality-Weighted 2-Clustering with Given Center Problem

Standard

Exact Algorithm for the One-Dimensional Quadratic Euclidean Cardinality-Weighted 2-Clustering with Given Center Problem. / Khandeev, Vladimir ; Panasenko, Anna.

Mathematical Optimization Theory and Operations Research - 19th International Conference, MOTOR 2020, Revised Selected Papers. ed. / Yury Kochetov; Igor Bykadorov; Tatiana Gruzdeva. Springer Science and Business Media Deutschland GmbH, 2020. p. 30-35 (Communications in Computer and Information Science; Vol. 1275 CCIS).

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

Harvard

Khandeev, V & Panasenko, A 2020, Exact Algorithm for the One-Dimensional Quadratic Euclidean Cardinality-Weighted 2-Clustering with Given Center Problem. in Y Kochetov, I Bykadorov & T Gruzdeva (eds), Mathematical Optimization Theory and Operations Research - 19th International Conference, MOTOR 2020, Revised Selected Papers. Communications in Computer and Information Science, vol. 1275 CCIS, Springer Science and Business Media Deutschland GmbH, pp. 30-35, 19th International Conference on Mathematical Optimization Theory and Operations Research,MOTOR 2020, Novosibirsk, Russian Federation, 06.07.2020. https://doi.org/10.1007/978-3-030-58657-7_4

APA

Khandeev, V., & Panasenko, A. (2020). Exact Algorithm for the One-Dimensional Quadratic Euclidean Cardinality-Weighted 2-Clustering with Given Center Problem. In Y. Kochetov, I. Bykadorov, & T. Gruzdeva (Eds.), Mathematical Optimization Theory and Operations Research - 19th International Conference, MOTOR 2020, Revised Selected Papers (pp. 30-35). (Communications in Computer and Information Science; Vol. 1275 CCIS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-030-58657-7_4

Vancouver

Khandeev V , Panasenko A. Exact Algorithm for the One-Dimensional Quadratic Euclidean Cardinality-Weighted 2-Clustering with Given Center Problem. In Kochetov Y, Bykadorov I, Gruzdeva T, editors, Mathematical Optimization Theory and Operations Research - 19th International Conference, MOTOR 2020, Revised Selected Papers. Springer Science and Business Media Deutschland GmbH. 2020. p. 30-35. (Communications in Computer and Information Science). doi: 10.1007/978-3-030-58657-7_4

Author

Khandeev, Vladimir ; Panasenko, Anna. / Exact Algorithm for the One-Dimensional Quadratic Euclidean Cardinality-Weighted 2-Clustering with Given Center Problem. Mathematical Optimization Theory and Operations Research - 19th International Conference, MOTOR 2020, Revised Selected Papers. editor / Yury Kochetov ; Igor Bykadorov ; Tatiana Gruzdeva. Springer Science and Business Media Deutschland GmbH, 2020. pp. 30-35 (Communications in Computer and Information Science).

BibTeX

@inproceedings{caa4ae33fd9541e387d77fd181b98b8f,

title = "Exact Algorithm for the One-Dimensional Quadratic Euclidean Cardinality-Weighted 2-Clustering with Given Center Problem",

abstract = "We consider a strongly NP-hard problem of clustering a finite set of points in Euclidean space into two clusters. In this problem, we find a partition of the input set minimizing the sum over both clusters of the weighted intracluster sums of the squared distances between the elements of the clusters and their centers. The weight factors are the cardinalities of the corresponding clusters and the centers are defined as follows. The center of the first cluster is unknown and determined as the centroid, while the center of the other one is given as input (is the origin without loss of generality). In this paper, we present a polynomial-time exact algorithm for the one-dimensional case of the problem.",

keywords = "Euclidean space, Exact algorithm, Minimum sum-of-squares, NP-hard problem, One-dimensional case, Polynomial-time, Weighted clustering",

author = "Vladimir Khandeev and Anna Panasenko",

note = "Publisher Copyright: {\textcopyright} 2020, Springer Nature Switzerland AG. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.; 19th International Conference on Mathematical Optimization Theory and Operations Research,MOTOR 2020 ; Conference date: 06-07-2020 Through 10-07-2020",

year = "2020",

month = jul,

doi = "10.1007/978-3-030-58657-7_4",

language = "English",

isbn = "9783030586560",

series = "Communications in Computer and Information Science",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "30--35",

editor = "Yury Kochetov and Igor Bykadorov and Tatiana Gruzdeva",

booktitle = "Mathematical Optimization Theory and Operations Research - 19th International Conference, MOTOR 2020, Revised Selected Papers",

address = "Germany",

}

RIS

TY - GEN

T1 - Exact Algorithm for the One-Dimensional Quadratic Euclidean Cardinality-Weighted 2-Clustering with Given Center Problem

AU - Khandeev, Vladimir

AU - Panasenko, Anna

PY - 2020/7

Y1 - 2020/7

N2 - We consider a strongly NP-hard problem of clustering a finite set of points in Euclidean space into two clusters. In this problem, we find a partition of the input set minimizing the sum over both clusters of the weighted intracluster sums of the squared distances between the elements of the clusters and their centers. The weight factors are the cardinalities of the corresponding clusters and the centers are defined as follows. The center of the first cluster is unknown and determined as the centroid, while the center of the other one is given as input (is the origin without loss of generality). In this paper, we present a polynomial-time exact algorithm for the one-dimensional case of the problem.

AB - We consider a strongly NP-hard problem of clustering a finite set of points in Euclidean space into two clusters. In this problem, we find a partition of the input set minimizing the sum over both clusters of the weighted intracluster sums of the squared distances between the elements of the clusters and their centers. The weight factors are the cardinalities of the corresponding clusters and the centers are defined as follows. The center of the first cluster is unknown and determined as the centroid, while the center of the other one is given as input (is the origin without loss of generality). In this paper, we present a polynomial-time exact algorithm for the one-dimensional case of the problem.

KW - Euclidean space

KW - Exact algorithm

KW - Minimum sum-of-squares

KW - NP-hard problem

KW - One-dimensional case

KW - Polynomial-time

KW - Weighted clustering

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

U2 - 10.1007/978-3-030-58657-7_4

DO - 10.1007/978-3-030-58657-7_4

M3 - Conference contribution

AN - SCOPUS:85092074622

SN - 9783030586560

T3 - Communications in Computer and Information Science

SP - 30

EP - 35

BT - Mathematical Optimization Theory and Operations Research - 19th International Conference, MOTOR 2020, Revised Selected Papers

A2 - Kochetov, Yury

A2 - Bykadorov, Igor

A2 - Gruzdeva, Tatiana

PB - Springer Science and Business Media Deutschland GmbH

T2 - 19th International Conference on Mathematical Optimization Theory and Operations Research,MOTOR 2020

Y2 - 6 July 2020 through 10 July 2020

ER -

ID: 25674900