RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Guidelines for authors Submit a manuscript Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Avtomat. i Telemekh.: Year: Volume: Issue: Page: Find

 Avtomat. i Telemekh., 2017, Issue 1, Pages 80–90 (Mi at14658)

System Analysis and Operations Research

Exact pseudopolynomial algorithm for one sequence partitioning problem

A. V. Kel'manovab, S. A. Khamidullina, V. I. Khandeevab

a Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences, Novosibirsk, Russia
b Novosibirsk State University, Novosibirsk, Russia

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: partition, sequence of vectors, Euclidean space, minimal sum of squared distances, NP-hardness, exact pseudopolynomial algorithm.

 Funding Agency Grant Number Russian Foundation for Basic Research 15-01-0046216-07-0016816-31-00186-ìîë-à This work was supported by the Russian Foundation for Basic Research, projects nos. 15-01-00462, 16-07-00168, and 16-31-00186-mol-a.

Full text: PDF file (644 kB)
References: PDF file   HTML file

English version:
Automation and Remote Control, 2017, 78:1, 67–74

Bibliographic databases:

Presented by the member of Editorial Board: À. À. Ëàçàðåâ

Citation: A. V. Kel'manov, S. A. Khamidullin, V. I. Khandeev, “Exact pseudopolynomial algorithm for one sequence partitioning problem”, Avtomat. i Telemekh., 2017, no. 1, 80–90; Autom. Remote Control, 78:1 (2017), 67–74

Citation in format AMSBIB
\Bibitem{KelKhaKha17} \by A.~V.~Kel'manov, S.~A.~Khamidullin, V.~I.~Khandeev \paper Exact pseudopolynomial algorithm for one sequence partitioning problem \jour Avtomat. i Telemekh. \yr 2017 \issue 1 \pages 80--90 \mathnet{http://mi.mathnet.ru/at14658} \elib{http://elibrary.ru/item.asp?id=28317448} \transl \jour Autom. Remote Control \yr 2017 \vol 78 \issue 1 \pages 67--74 \crossref{https://doi.org/10.1134/S0005117917010052} \isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000394180700005} \scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85011807605} 

• http://mi.mathnet.ru/eng/at14658
• http://mi.mathnet.ru/eng/at/y2017/i1/p80

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. Kel'manov A., “Efficient Approximation Algorithms For Some NP-Hard Problems of Partitioning a Set and a Sequence”, 2017 International Multi-Conference on Engineering, Computer and Information Sciences (SIBIRCON), IEEE, 2017, 87–90
2. A. Kel'manov, S. Khamidullin, V. Khandeev, “A randomized algorithm for 2-partition of a sequence”, Analysis of Images, Social Networks and Texts, AIST 2017, Lecture Notes in Computer Science, 10716, eds. W. van der Aalst, D. Ignatov, M. Khachay, S. Kuznetsov, V. Lempitsky, I. Lomazova, N. Loukachevitch, Springer, 2018, 313–322
3. A. V. Kel'manov, S. A. Khamidullin, V. I. Khandeev, “A randomized algorithm for a sequence 2-clustering problem”, Comput. Math. Math. Phys., 58:12 (2018), 2078–2085
•  Number of views: This page: 207 Full text: 7 References: 24 First page: 33