Standard

A PTAS for one cardinality-weighted 2-clustering problem. / Panasenko, Anna.

Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Proceedings. ed. / Michael Khachay; Panos Pardalos; Yury Kochetov. Springer-Verlag GmbH and Co. KG, 2019. p. 581-592 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11548 LNCS).

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

Harvard

Panasenko, A 2019, A PTAS for one cardinality-weighted 2-clustering problem. in M Khachay, P Pardalos & Y Kochetov (eds), Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11548 LNCS, Springer-Verlag GmbH and Co. KG, pp. 581-592, 18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019, Ekaterinburg, Russian Federation, 08.07.2019. https://doi.org/10.1007/978-3-030-22629-9_41

APA

Panasenko, A. (2019). A PTAS for one cardinality-weighted 2-clustering problem. In M. Khachay, P. Pardalos, & Y. Kochetov (Eds.), Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Proceedings (pp. 581-592). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11548 LNCS). Springer-Verlag GmbH and Co. KG. https://doi.org/10.1007/978-3-030-22629-9_41

Vancouver

Panasenko A. A PTAS for one cardinality-weighted 2-clustering problem. In Khachay M, Pardalos P, Kochetov Y, editors, Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Proceedings. Springer-Verlag GmbH and Co. KG. 2019. p. 581-592. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-22629-9_41

Author

Panasenko, Anna. / A PTAS for one cardinality-weighted 2-clustering problem. Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Proceedings. editor / Michael Khachay ; Panos Pardalos ; Yury Kochetov. Springer-Verlag GmbH and Co. KG, 2019. pp. 581-592 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{92fca3d21d1249439c680d5b0c910b05,
title = "A PTAS for one cardinality-weighted 2-clustering problem",
abstract = "We consider one strongly NP-hard problem of clustering a finite set of points in Euclidean space. In this problem, we need to partition a finite set of points into two clusters minimizing the sum over both clusters of the weighted intracluster sums. Each of these sums is the sum of squared distances between the elements of the cluster and their center. The center of the one cluster is unknown and determined as the centroid, while the center of the other one is fixed at the origin. The weight factors for both intracluster sums are the given sizes of the clusters. In this paper, we present an approximation algorithm for the problem and prove that it is a polynomial-time approximation scheme (PTAS).",
keywords = "Approximation algorithm, Euclidean space, NP-hardness, PTAS, Quadratic variation, Weighted 2-clustering, APPROXIMATION SCHEME, ALGORITHM",
author = "Anna Panasenko",
year = "2019",
month = jan,
day = "1",
doi = "10.1007/978-3-030-22629-9_41",
language = "English",
isbn = "9783030226282",
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 = "581--592",
editor = "Michael Khachay and Panos Pardalos and Yury Kochetov",
booktitle = "Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Proceedings",
address = "Germany",
note = "18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019 ; Conference date: 08-07-2019 Through 12-07-2019",

}

RIS

TY - GEN

T1 - A PTAS for one cardinality-weighted 2-clustering problem

AU - Panasenko, Anna

PY - 2019/1/1

Y1 - 2019/1/1

N2 - We consider one strongly NP-hard problem of clustering a finite set of points in Euclidean space. In this problem, we need to partition a finite set of points into two clusters minimizing the sum over both clusters of the weighted intracluster sums. Each of these sums is the sum of squared distances between the elements of the cluster and their center. The center of the one cluster is unknown and determined as the centroid, while the center of the other one is fixed at the origin. The weight factors for both intracluster sums are the given sizes of the clusters. In this paper, we present an approximation algorithm for the problem and prove that it is a polynomial-time approximation scheme (PTAS).

AB - We consider one strongly NP-hard problem of clustering a finite set of points in Euclidean space. In this problem, we need to partition a finite set of points into two clusters minimizing the sum over both clusters of the weighted intracluster sums. Each of these sums is the sum of squared distances between the elements of the cluster and their center. The center of the one cluster is unknown and determined as the centroid, while the center of the other one is fixed at the origin. The weight factors for both intracluster sums are the given sizes of the clusters. In this paper, we present an approximation algorithm for the problem and prove that it is a polynomial-time approximation scheme (PTAS).

KW - Approximation algorithm

KW - Euclidean space

KW - NP-hardness

KW - PTAS

KW - Quadratic variation

KW - Weighted 2-clustering

KW - APPROXIMATION SCHEME

KW - ALGORITHM

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

U2 - 10.1007/978-3-030-22629-9_41

DO - 10.1007/978-3-030-22629-9_41

M3 - Conference contribution

AN - SCOPUS:85067701136

SN - 9783030226282

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

SP - 581

EP - 592

BT - Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Proceedings

A2 - Khachay, Michael

A2 - Pardalos, Panos

A2 - Kochetov, Yury

PB - Springer-Verlag GmbH and Co. KG

T2 - 18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019

Y2 - 8 July 2019 through 12 July 2019

ER -

ID: 20643379