Standard

Exact pseudopolynomial algorithm for one sequence partitioning problem. / Kel’manov, A. V.; Khamidullin, S. A.; Khandeev, V. I.

In: Automation and Remote Control, Vol. 78, No. 1, 01.01.2017, p. 67-74.

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

Harvard

Kel’manov, AV, Khamidullin, SA & Khandeev, VI 2017, 'Exact pseudopolynomial algorithm for one sequence partitioning problem', Automation and Remote Control, vol. 78, no. 1, pp. 67-74. https://doi.org/10.1134/S0005117917010052

APA

Kel’manov, A. V., Khamidullin, S. A., & Khandeev, V. I. (2017). Exact pseudopolynomial algorithm for one sequence partitioning problem. Automation and Remote Control, 78(1), 67-74. https://doi.org/10.1134/S0005117917010052

Vancouver

Kel’manov AV, Khamidullin SA, Khandeev VI. Exact pseudopolynomial algorithm for one sequence partitioning problem. Automation and Remote Control. 2017 Jan 1;78(1):67-74. doi: 10.1134/S0005117917010052

Author

Kel’manov, A. V. ; Khamidullin, S. A. ; Khandeev, V. I. / Exact pseudopolynomial algorithm for one sequence partitioning problem. In: Automation and Remote Control. 2017 ; Vol. 78, No. 1. pp. 67-74.

BibTeX

@article{967277071beb4286bdf3475329f6f7c4,
title = "Exact pseudopolynomial algorithm for one sequence partitioning problem",
abstract = "We consider a strongly NP-hard problem of partitioning a finite sequence of vectors in a Euclidean space into two clusters of given size with the criterion of minimizing the total sum of square distances from cluster elements to their centers. The center of the first cluster is subject to optimization, defined by the mean value of all vectors in this cluster. The center of the second cluster is fixed at the origin. The partition is subject to the following condition: the difference between indices of two subsequent vectors included in the first cluster is bounded from above and below by given constants. We propose an exact pseudopolynomial algorithm for the case of a problem where the dimension of the space is fixed, and components of input vectors are integer-valued.",
keywords = "Euclidean space, exact pseudopolynomial algorithm, minimal sum of squared distances, NP-hardness, partition, sequence of vectors",
author = "Kel{\textquoteright}manov, {A. V.} and Khamidullin, {S. A.} and Khandeev, {V. I.}",
year = "2017",
month = jan,
day = "1",
doi = "10.1134/S0005117917010052",
language = "English",
volume = "78",
pages = "67--74",
journal = "Automation and Remote Control",
issn = "0005-1179",
publisher = "Maik Nauka-Interperiodica Publishing",
number = "1",

}

RIS

TY - JOUR

T1 - Exact pseudopolynomial algorithm for one sequence partitioning problem

AU - Kel’manov, A. V.

AU - Khamidullin, S. A.

AU - Khandeev, V. I.

PY - 2017/1/1

Y1 - 2017/1/1

N2 - We consider a strongly NP-hard problem of partitioning a finite sequence of vectors in a Euclidean space into two clusters of given size with the criterion of minimizing the total sum of square distances from cluster elements to their centers. The center of the first cluster is subject to optimization, defined by the mean value of all vectors in this cluster. The center of the second cluster is fixed at the origin. The partition is subject to the following condition: the difference between indices of two subsequent vectors included in the first cluster is bounded from above and below by given constants. We propose an exact pseudopolynomial algorithm for the case of a problem where the dimension of the space is fixed, and components of input vectors are integer-valued.

AB - We consider a strongly NP-hard problem of partitioning a finite sequence of vectors in a Euclidean space into two clusters of given size with the criterion of minimizing the total sum of square distances from cluster elements to their centers. The center of the first cluster is subject to optimization, defined by the mean value of all vectors in this cluster. The center of the second cluster is fixed at the origin. The partition is subject to the following condition: the difference between indices of two subsequent vectors included in the first cluster is bounded from above and below by given constants. We propose an exact pseudopolynomial algorithm for the case of a problem where the dimension of the space is fixed, and components of input vectors are integer-valued.

KW - Euclidean space

KW - exact pseudopolynomial algorithm

KW - minimal sum of squared distances

KW - NP-hardness

KW - partition

KW - sequence of vectors

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

U2 - 10.1134/S0005117917010052

DO - 10.1134/S0005117917010052

M3 - Article

AN - SCOPUS:85011807605

VL - 78

SP - 67

EP - 74

JO - Automation and Remote Control

JF - Automation and Remote Control

SN - 0005-1179

IS - 1

ER -

ID: 10312518