NP-Hardness of Some Euclidean Problems of Partitioning a Finite Set of Points


Cite item

Full Text

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

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).

About the authors

A. V. Kel’manov

Sobolev Institute of Mathematics, Siberian Branch; Novosibirsk State University

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

A. V. Pyatkin

Sobolev Institute of Mathematics, Siberian Branch; Novosibirsk State University

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

Supplementary files

Supplementary Files
Action
1. JATS XML

Copyright (c) 2018 Pleiades Publishing, Ltd.