Standard

Pseudopolynomial time solvability of a quadratic Euclidean problem of finding a family of disjoint subsets. / Galashov, A. E.; Kel’manov, A. V.

In: Numerical Analysis and Applications, Vol. 10, No. 1, 01.01.2017, p. 11-16.

Research output: Contribution to journal › Article › peer-review

Harvard

Galashov, AE & Kel’manov, AV 2017, 'Pseudopolynomial time solvability of a quadratic Euclidean problem of finding a family of disjoint subsets', Numerical Analysis and Applications, vol. 10, no. 1, pp. 11-16. https://doi.org/10.1134/S1995423917010025

APA

Galashov, A. E., & Kel’manov, A. V. (2017). Pseudopolynomial time solvability of a quadratic Euclidean problem of finding a family of disjoint subsets. Numerical Analysis and Applications, 10(1), 11-16. https://doi.org/10.1134/S1995423917010025

Vancouver

Galashov AE, Kel’manov AV. Pseudopolynomial time solvability of a quadratic Euclidean problem of finding a family of disjoint subsets. Numerical Analysis and Applications. 2017 Jan 1;10(1):11-16. doi: 10.1134/S1995423917010025

Author

Galashov, A. E. ; Kel’manov, A. V. / Pseudopolynomial time solvability of a quadratic Euclidean problem of finding a family of disjoint subsets. In: Numerical Analysis and Applications. 2017 ; Vol. 10, No. 1. pp. 11-16.

BibTeX

@article{02a8215d56f247f0b510b140bb352c0f,
title = "Pseudopolynomial time solvability of a quadratic Euclidean problem of finding a family of disjoint subsets",
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.",
keywords = "clustering, Euclidean space, exact pseudopolynomial time algorithm, NP-hard problem, subsets search",
author = "Galashov, {A. E.} and Kel{\textquoteright}manov, {A. V.}",
year = "2017",
month = jan,
day = "1",
doi = "10.1134/S1995423917010025",
language = "English",
volume = "10",
pages = "11--16",
journal = "Numerical Analysis and Applications",
issn = "1995-4239",
publisher = "Maik Nauka-Interperiodica Publishing",
number = "1",

}

RIS

TY - JOUR

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

AU - Galashov, A. E.

AU - Kel’manov, A. V.

PY - 2017/1/1

Y1 - 2017/1/1

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

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

KW - clustering

KW - Euclidean space

KW - exact pseudopolynomial time algorithm

KW - NP-hard problem

KW - subsets search

UR - http://www.scopus.com/inward/record.url?scp=85014770273&partnerID=8YFLogxK

U2 - 10.1134/S1995423917010025

DO - 10.1134/S1995423917010025

M3 - Article

AN - SCOPUS:85014770273

VL - 10

SP - 11

EP - 16

JO - Numerical Analysis and Applications

JF - Numerical Analysis and Applications

SN - 1995-4239

IS - 1

ER -

ID: 9056388