@inproceedings{a4043a7f7fd74af097710355ff6c3c93,
title = "An approximation scheme for a weighted two-cluster partition problem",
abstract = "We consider the problem of partitioning a set of Euclidean points into two clusters to minimize the weighted sum of the squared intracluster distances from the elements of the clusters to their centers. The center of one of the clusters is unknown and determined as the average value over all points in the cluster, while the center of the other cluster is the origin. The weight factors for both intracluster sums are given as input. We present an approximation algorithm for the problem, which is based on an adaptive-grid-approach. The algorithm implements a fully polynomial-time approximation scheme (FPTAS) in the case of the fixed space dimension. In the case when the dimension of space is not fixed but is bounded by a slowly growing function of the number of input points, the algorithm realizes a polynomial-time approximation scheme (PTAS).",
keywords = "Euclidean space, FPTAS, NP-hardness, PTAS, Weighted 2-clustering, Euclidean space FPTAS, SET, COMPLEXITY, VECTORS, CLUSTER-ANALYSIS",
author = "Alexander Kel{\textquoteright}manov and Anna Motkova and Vladimir Shenmaier",
year = "2018",
month = jan,
day = "1",
doi = "10.1007/978-3-319-73013-4_30",
language = "English",
isbn = "9783319730127",
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 = "323--333",
editor = "WMP VanDerAalst and DI Ignatov and M Khachay and SO Kuznetsov and Lempitsky and IA Lomazova and N Loukachevitch and A Napoli and A Panchenko and PM Pardalos and AV Savchenko and S Wasserman",
booktitle = "Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers",
address = "Germany",
note = "6th International Conference on Analysis of Images, Social Networks and Texts, AIST 2017 ; Conference date: 27-07-2017 Through 29-07-2017",
}