RUS  ENG
Full version
JOURNALS // Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki // Archive

Zh. Vychisl. Mat. Mat. Fiz., 2018 Volume 58, Number 5, Pages 852–856 (Mi zvmmf10742)

This article is cited in 5 papers

Np-hardness of some Euclidean problems of partitioning a finite set of points

A. V. Kel'manovab, A. V. Pyatkinab

a Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences, Novosibirsk, Russia
b Novosibirsk State University, Novosibirsk, Russia

Abstract: Problems of partitioning a finite set of Euclidean points (vectors) into clusters are considered. The criterion is to minimize the sum, over all clusters, of (1) squared norms of the sums of cluster elements normalized by the cardinality, (2) squared norms of the sums of cluster elements, and (3) norms of the sum of cluster elements. It is proved that all these problems are strongly NP-hard if the number of clusters is a part of the input and are NP-hard in the ordinary sense if the number of clusters is not a part of the input (is fixed). Moreover, the problems are NP-hard even in the case of dimension 1 (on a line).

Key words: partitioning, Euclidean space, norm of sum, NP-hardness.

UDC: 519.72

Received: 06.06.2016

DOI: 10.7868/S0044466918050149


 English version:
Computational Mathematics and Mathematical Physics, 2018, 58:5, 822–826

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025