@inproceedings{0e22a252d53a4445bc21b394a6fabd9c,
title = "2-Approximation Polynomial-Time Algorithm for a 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 clusters of the given sizes with some constraints. The solution criterion is the minimum of the sum of weighted intracluster sums of squared distances between the elements of each cluster and its center. The weight of the intracluster sum is equal to the cluster size. The center of one cluster is given as input (is the origin without loss of generality), while the center of the other one is unknown and is determined as a geometric center. 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 some given constants. In this paper, we have shown that the considered problem is the strongly NP-hard one and propose a polynomial-time 2-approximation algorithm for solving the problem.",
keywords = "Approximation algorithm, Euclidean space, NP-hard problem, Polynomial time, Quadratic variation, Sequence of points, Weighted 2-partition",
author = "Alexander Kel{\textquoteright}manov and Sergey Khamidullin and Anna Panasenko",
year = "2020",
month = jan,
day = "1",
doi = "10.1007/978-3-030-40616-5_34",
language = "English",
isbn = "9783030406158",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Gabler",
pages = "386--393",
editor = "Sergeyev, {Yaroslav D.} and Kvasov, {Dmitri E.}",
booktitle = "Numerical Computations",
address = "Germany",
note = "3rd Triennial International Conference and Summer School on Numerical Computations: Theory and Algorithms, NUMTA 2019 ; Conference date: 15-06-2019 Through 21-06-2019",
}