Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS


Zh. Vychisl. Mat. Mat. Fiz.:
Year:
Volume:
Issue:
Page:
Find




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

Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki, 2015, Volume 55, Number 2, Pages 335–344
DOI: https://doi.org/10.7868/S0044466915020131 (Mi zvmmf10162) 		 
This article is cited in 28 scientific papers (total in 28 papers)

A randomized algorithm for two-cluster partition of a set of vectors

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

a Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences, pr. Akademika Koptyuga 4, Novosibirsk, 630090, Russia
b Novosibirsk State University, ul. Pirogova 2, Novosibirsk, 630090, Russia
Full-text PDF (240 kB) Citations (28)
References:
PDF
HTML
DOI: https://doi.org/10.7868/S0044466915020131
Abstract: A randomized algorithm is substantiated for the strongly NP-hard problem of partitioning a finite set of vectors of Euclidean space into two clusters of given sizes according to the minimum-of-the sum-of-squared-distances criterion. It is assumed that the centroid of one of the clusters is to be optimized and is determined as the mean value over all vectors in this cluster. The centroid of the other cluster is fixed at the origin. For an established parameter value, the algorithm finds an approximate solution of the problem in time that is linear in the space dimension and the input size of the problem for given values of the relative error and failure probability. The conditions are established under which the algorithm is asymptotically exact and runs in time that is linear in the space dimension and quadratic in the input size of the problem.
Key words: partition, set of vectors, squared Euclidean distances, NP-hardness, randomized algorithm, asymptotic accuracy.
Funding agency Grant number
Russian Foundation for Basic Research 15-00-00462
13-07-00070
Received: 12.03.2014
English version:
Computational Mathematics and Mathematical Physics, 2015, Volume 55, Issue 2, Pages 330–339
DOI: https://doi.org/10.1134/S096554251502013X
Bibliographic databases:
Document Type: Article
UDC: 519.7
Language: Russian
Citation: A. V. Kel'manov, V. I. Khandeev, “A randomized algorithm for two-cluster partition of a set of vectors”, Zh. Vychisl. Mat. Mat. Fiz., 55:2 (2015), 335–344; Comput. Math. Math. Phys., 55:2 (2015), 330–339
Citation in format AMSBIB
\Bibitem{KelKha15}
\by A.~V.~Kel'manov, V.~I.~Khandeev
\paper A randomized algorithm for two-cluster partition of a set of vectors
\jour Zh. Vychisl. Mat. Mat. Fiz.
\yr 2015
\vol 55
\issue 2
\pages 335--344
\mathnet{http://mi.mathnet.ru/zvmmf10162}
\crossref{https://doi.org/10.7868/S0044466915020131}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3317887}
\elib{https://elibrary.ru/item.asp?id=22908475}
\transl
\jour Comput. Math. Math. Phys.
\yr 2015
\vol 55
\issue 2
\pages 330--339
\crossref{https://doi.org/10.1134/S096554251502013X}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000350801800017}
\elib{https://elibrary.ru/item.asp?id=24011263}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84924119914}
Linking options:
  • https://www.mathnet.ru/eng/zvmmf10162
  • https://www.mathnet.ru/eng/zvmmf/v55/i2/p335
    • This publication is cited in the following 28 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Журнал вычислительной математики и математической физики Computational Mathematics and Mathematical Physics
    Statistics & downloads:
    Abstract page:348
    Full-text PDF :63
    References:70
    First page:19
     
      Contact us:
    		  Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024