Pseudopolynomial time solvability of a quadratic Euclidean problem of finding a family of disjoint subsets
- Authors: Galashov A.E.1, Kel’manov A.V.1,2
-
Affiliations:
- Novosibirsk State University
- Sobolev Institute ofMathematics, Siberian Branch
- Issue: Vol 10, No 1 (2017)
- Pages: 11-16
- Section: Article
- URL: https://journals.rcsi.science/1995-4239/article/view/197753
- DOI: https://doi.org/10.1134/S1995423917010025
- ID: 197753
Cite item
Abstract
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.
About the authors
A. E. Galashov
Novosibirsk State University
Author for correspondence.
Email: galashov.alexandr@gmail.com
Russian Federation, ul. Pirogova 2, Novosibirsk, 630090
A. V. Kel’manov
Novosibirsk State University; Sobolev Institute ofMathematics, Siberian Branch
Email: galashov.alexandr@gmail.com
Russian Federation, ul. Pirogova 2, Novosibirsk, 630090; pr. Akad. Koptyuga 4, Novosibirsk, 630090