Pseudopolynomial time solvability of a quadratic Euclidean problem of finding a family of disjoint subsets

A. E. Galashov, A. V. Kel’manov

Результат исследования: Научные публикации в периодических изданияхстатья

1 Цитирования (Scopus)

Аннотация

In this paper, a strongly NP-hard problem of finding a family of disjoint subsets with given cardinalities in a finite set of points from a Euclidean space is considered. Minimization of the sum over all required subsets of the sum of the squared distances from the elements of these subsets to their geometric centers is used as the search criterion. It is proved that if the coordinates of the input points are integer and the space dimension and the number of required subsets are fixed (i.e., bounded by some constants), the problem is a pseudopolynomial time solvable one.

Язык оригиналаанглийский
Страницы (с-по)11-16
Число страниц6
ЖурналNumerical Analysis and Applications
Том10
Номер выпуска1
DOI
СостояниеОпубликовано - 1 янв 2017

Fingerprint Подробные сведения о темах исследования «Pseudopolynomial time solvability of a quadratic Euclidean problem of finding a family of disjoint subsets». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать