Avtomatika i Telemekhanika
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




Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register

Avtomatika i Telemekhanika, 2017, Issue 1, Pages 80–90 (Mi at14658)  
This article is cited in 6 scientific papers (total in 6 papers)

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
Full-text PDF (644 kB) Citations (6)
References:
PDF
HTML
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-00462
16-07-00168
16-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.
Presented by the member of Editorial Board: A. A. Lazarev

Received: 12.01.2015
English version:
Automation and Remote Control, 2017, Volume 78, Issue 1, Pages 67–74
DOI: https://doi.org/10.1134/S0005117917010052
Bibliographic databases:
Document Type: Article
Language: Russian
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{https://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{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000394180700005}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85011807605}
Linking options:
  • https://www.mathnet.ru/eng/at14658
  • https://www.mathnet.ru/eng/at/y2017/i1/p80
    • This publication is cited in the following 6 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Avtomatika i Telemekhanika
    Statistics & downloads:
    Abstract page:344
    Full-text PDF :37
    References:35
    First page:33
     
      Contact us:
    		  Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024