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, 2018, Volume 58, Number 1, Pages 136–142
DOI: https://doi.org/10.7868/S0044466918010076 (Mi zvmmf10665) 		 
This article is cited in 8 scientific papers (total in 8 papers)

Polynomial-time approximation algorithm for the problem of cardinality-weighted variance-based 2-clustering with a given center

A. V. Kel'manovab, A. V. Motkovaab

a Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences, Novosibirsk, Russia
b Novosibirsk State University, Novosibirsk, Russia
Citations (8)
References:
PDF
HTML
DOI: https://doi.org/10.7868/S0044466918010076
Abstract: A strongly NP-hard problem of partitioning a finite set of points of Euclidean space into two clusters is considered. The solution criterion is the minimum of the sum (over both clusters) of weighted sums of squared distances from the elements of each cluster to its geometric center. The weights of the sums are equal to the cardinalities of the desired clusters. The center of one cluster is given as input, while the center of the other is unknown and is determined as the point of space equal to the mean of the cluster elements. A version of the problem is analyzed in which the cardinalities of the clusters are given as input. A polynomial-time 2-approximation algorithm for solving the problem is constructed.
Key words: Euclidean space, weighted 2-clustering, NP-hardness, polynomial-time 2-approximation algorithm.
Funding agency Grant number
Russian Science Foundation 16-11-10041
Received: 18.06.2016
Revised: 20.07.2017
English version:
Computational Mathematics and Mathematical Physics, 2018, Volume 58, Issue 1, Pages 130–136
DOI: https://doi.org/10.1134/S0965542518010074
Bibliographic databases:
Document Type: Article
UDC: 519.7
Language: Russian
Citation: A. V. Kel'manov, A. V. Motkova, “Polynomial-time approximation algorithm for the problem of cardinality-weighted variance-based 2-clustering with a given center”, Zh. Vychisl. Mat. Mat. Fiz., 58:1 (2018), 136–142; Comput. Math. Math. Phys., 58:1 (2018), 130–136
Citation in format AMSBIB
\Bibitem{KelMot18}
\by A.~V.~Kel'manov, A.~V.~Motkova
\paper Polynomial-time approximation algorithm for the problem of cardinality-weighted variance-based 2-clustering with a given center
\jour Zh. Vychisl. Mat. Mat. Fiz.
\yr 2018
\vol 58
\issue 1
\pages 136--142
\mathnet{http://mi.mathnet.ru/zvmmf10665}
\crossref{https://doi.org/10.7868/S0044466918010076}
\elib{https://elibrary.ru/item.asp?id=32282721}
\transl
\jour Comput. Math. Math. Phys.
\yr 2018
\vol 58
\issue 1
\pages 130--136
\crossref{https://doi.org/10.1134/S0965542518010074}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000426674100009}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85042701688}
Linking options:
  • https://www.mathnet.ru/eng/zvmmf10665
  • https://www.mathnet.ru/eng/zvmmf/v58/i1/p136
    • This publication is cited in the following 8 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Журнал вычислительной математики и математической физики Computational Mathematics and Mathematical Physics
     
      Contact us:
    		  Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024