This article is cited in 16 papers

An exact pseudopolynomial algorithm for a bi-partitioning problem

A. V. Kel'manov^ab, V. I. Khandeev<sup>b

a</sup> Novosibirsk State University, 2 Pirogov St., 630090 Novosibirsk, Russia
^b Sobolev Institute of Mathematics, 4 Koptyug Ave., 630090 Novosibirsk, Russia

Abstract: We consider the strongly NP-hard problem of partitioning a set of Euclidean vectors into two sets (clusters) under the criterion of minimum sum-of-squared distances from the elements of clusters to their centers. The center of the first cluster is the average value of the vectors in the cluster, and the center of the second one is the origin. We prove that the problem is solvable in polynomial time in the case of fixed space dimension. We also present a pseudopolynomial algorithm which finds an optimal solution in the case of integer values of the components of the vectors in the input set and fixed space dimension. Bibliogr. 27.

Keywords: bi-partitioning, vector subset, squared Euclidean distances, NP-hardness, exact pseudopolynomial algorithm.

UDC: 519.16+519.85

Received: 16.09.2014
Revised: 22.02.2015

DOI: 10.17377/daio.2015.22.463

 English version: Journal of Applied and Industrial Mathematics, 2015, 9:4, 497–502

Bibliographic databases:

• 
•