Diskretnyi Analiz i Issledovanie Operatsii
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor
Guidelines for authors

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS


Diskretn. Anal. Issled. Oper.:
Year:
Volume:
Issue:
Page:
Find




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

Diskretnyi Analiz i Issledovanie Operatsii, 2015, Volume 22, Issue 4, Pages 50–62
DOI: https://doi.org/10.17377/daio.2015.22.463 (Mi da824) 		 
This article is cited in 16 scientific papers (total in 16 papers)

An exact pseudopolynomial algorithm for a bi-partitioning problem

A. V. Kel'manovab, V. I. Khandeevb

a Novosibirsk State University, 2 Pirogov St., 630090 Novosibirsk, Russia
b Sobolev Institute of Mathematics, 4 Koptyug Ave., 630090 Novosibirsk, Russia
Full-text PDF (251 kB) Citations (16)
References:
PDF
HTML
DOI: https://doi.org/10.17377/daio.2015.22.463
Abstract: We consider the strongly NP-hard problem of partitioning a set of Euclidean vectors into two sets (clusters) under the criterion of minimum sum-of-squared distances from the elements of clusters to their centers. The center of the first cluster is the average value of the vectors in the cluster, and the center of the second one is the origin. We prove that the problem is solvable in polynomial time in the case of fixed space dimension. We also present a pseudopolynomial algorithm which finds an optimal solution in the case of integer values of the components of the vectors in the input set and fixed space dimension. Bibliogr. 27.
Keywords: bi-partitioning, vector subset, squared Euclidean distances, NP-hardness, exact pseudopolynomial algorithm.
Received: 16.09.2014
Revised: 22.02.2015
English version:
Journal of Applied and Industrial Mathematics, 2015, Volume 9, Issue 4, Pages 497–502
DOI: https://doi.org/10.1134/S1990478915040067
Bibliographic databases:
Document Type: Article
UDC: 519.16+519.85
Language: Russian
Citation: A. V. Kel'manov, V. I. Khandeev, “An exact pseudopolynomial algorithm for a bi-partitioning problem”, Diskretn. Anal. Issled. Oper., 22:4 (2015), 50–62; J. Appl. Industr. Math., 9:4 (2015), 497–502
Citation in format AMSBIB
\Bibitem{KelKha15}
\by A.~V.~Kel'manov, V.~I.~Khandeev
\paper An exact pseudopolynomial algorithm for a~bi-partitioning problem
\jour Diskretn. Anal. Issled. Oper.
\yr 2015
\vol 22
\issue 4
\pages 50--62
\mathnet{http://mi.mathnet.ru/da824}
\crossref{https://doi.org/10.17377/daio.2015.22.463}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3467235}
\elib{https://elibrary.ru/item.asp?id=23859897}
\transl
\jour J. Appl. Industr. Math.
\yr 2015
\vol 9
\issue 4
\pages 497--502
\crossref{https://doi.org/10.1134/S1990478915040067}
Linking options:
  • https://www.mathnet.ru/eng/da824
  • https://www.mathnet.ru/eng/da/v22/i4/p50
    • This publication is cited in the following 16 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Дискретный анализ и исследование операций
    Statistics & downloads:
    Abstract page:340
    Full-text PDF :85
    References:62
    First page:5
     
      Contact us:
    		  Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024