Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters


Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

Abstract

We consider the strongly NP-hard problem of partitioning a finite set of points of Euclidean space into two clusters of given cardinalities under the minimum criterion for the sum over the clusters of the intracluster sums of squared distances from elements of the cluster to its center. It is assumed that the center of one of the clusters is given (without loss of generality, at the origin). The center of the second cluster is unknown and is defined as the mean value over all elements in this cluster. A polynomial-time approximation scheme (PTAS) is provided.

About the authors

A. V. Dolgushev

Novosibirsk State University

Author for correspondence.
Email: dolgushev@math.nsc.ru
Russian Federation, Novosibirsk, 630090

A. V. Kel’manov

Novosibirsk State University; Sobolev Institute of Mathematics

Email: dolgushev@math.nsc.ru
Russian Federation, Novosibirsk, 630090; Novosibirsk, 630090

V. V. Shenmaier

Sobolev Institute of Mathematics

Email: dolgushev@math.nsc.ru
Russian Federation, Novosibirsk, 630090

Supplementary files

Supplementary Files
Action
1. JATS XML

Copyright (c) 2016 Pleiades Publishing, Ltd.