Trudy Instituta Matematiki i Mekhaniki UrO RAN
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


Trudy Inst. Mat. i Mekh. UrO RAN:
Year:
Volume:
Issue:
Page:
Find




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

Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2015, Volume 21, Number 3, Pages 100–109 (Mi timm1202)  
This article is cited in 19 scientific papers (total in 19 papers)

Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters

A. V. Dolgusheva, A. V. Kel'manovab, V. V. Shenmaierb

a Novosibirsk State University
b Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk
Full-text PDF (181 kB) Citations (19)
References:
PDF
HTML
Abstract: We consider the strongly $NP$-hard problem of partitioning a finite set of points of Euclidean space into two clusters of given cardinalities under the minimum criterion for the sum over the clusters of the intracluster sums of squared distances from elements of the cluster to its center. It is assumed that the center of one of the clusters is given (without loss of generality, at the origin). The center of the second cluster is unknown and is determined as the mean value over all elements in this cluster. A polynomial-time approximation scheme (PTAS) is provided.
Keywords: ptas, cluster analysis, euclidean space, $np$-hard problem, ptas.
Received: 27.04.2015
English version:
Proceedings of the Steklov Institute of Mathematics (Supplementary issues), 2016, Volume 295, Issue 1, Pages 47–56
DOI: https://doi.org/10.1134/S0081543816090066
Bibliographic databases:
Document Type: Article
UDC: 519.16+519.85
Language: Russian
Citation: A. V. Dolgushev, A. V. Kel'manov, V. V. Shenmaier, “Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters”, Trudy Inst. Mat. i Mekh. UrO RAN, 21, no. 3, 2015, 100–109; Proc. Steklov Inst. Math. (Suppl.), 295, suppl. 1 (2016), 47–56
Citation in format AMSBIB
\Bibitem{DolKelShe15}
\by A.~V.~Dolgushev, A.~V.~Kel'manov, V.~V.~Shenmaier
\paper Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters
\serial Trudy Inst. Mat. i Mekh. UrO RAN
\yr 2015
\vol 21
\issue 3
\pages 100--109
\mathnet{http://mi.mathnet.ru/timm1202}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3468093}
\elib{https://elibrary.ru/item.asp?id=24156699}
\transl
\jour Proc. Steklov Inst. Math. (Suppl.)
\yr 2016
\vol 295
\issue , suppl. 1
\pages 47--56
\crossref{https://doi.org/10.1134/S0081543816090066}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000394441400006}
Linking options:
  • https://www.mathnet.ru/eng/timm1202
  • https://www.mathnet.ru/eng/timm/v21/i3/p100
    • This publication is cited in the following 19 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Trudy Instituta Matematiki i Mekhaniki UrO RAN
    Statistics & downloads:
    Abstract page:271
    Full-text PDF :61
    References:39
    First page:9
     
      Contact us:
    		  Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024