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 5, Pages 852–856
DOI: https://doi.org/10.7868/S0044466918050149
(Mi zvmmf10742)
 

This article is cited in 5 scientific papers (total in 5 papers)

Np-hardness of some Euclidean problems of partitioning a finite set of points

A. V. Kel'manovab, A. V. Pyatkinab

a Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences, Novosibirsk, Russia
b Novosibirsk State University, Novosibirsk, Russia
Citations (5)
References:
Abstract: Problems of partitioning a finite set of Euclidean points (vectors) into clusters are considered. The criterion is to minimize the sum, over all clusters, of (1) squared norms of the sums of cluster elements normalized by the cardinality, (2) squared norms of the sums of cluster elements, and (3) norms of the sum of cluster elements. It is proved that all these problems are strongly NP-hard if the number of clusters is a part of the input and are NP-hard in the ordinary sense if the number of clusters is not a part of the input (is fixed). Moreover, the problems are NP-hard even in the case of dimension 1 (on a line).
Key words: partitioning, Euclidean space, norm of sum, NP-hardness.
Funding agency Grant number
Russian Science Foundation 16-11-10041
Received: 06.06.2016
English version:
Computational Mathematics and Mathematical Physics, 2018, Volume 58, Issue 5, Pages 822–826
DOI: https://doi.org/10.1134/S0965542518050123
Bibliographic databases:
Document Type: Article
UDC: 519.72
Language: Russian
Citation: A. V. Kel'manov, A. V. Pyatkin, “Np-hardness of some Euclidean problems of partitioning a finite set of points”, Zh. Vychisl. Mat. Mat. Fiz., 58:5 (2018), 852–856; Comput. Math. Math. Phys., 58:5 (2018), 822–826
Citation in format AMSBIB
\Bibitem{KelPya18}
\by A.~V.~Kel'manov, A.~V.~Pyatkin
\paper Np-hardness of some Euclidean problems of partitioning a finite set of points
\jour Zh. Vychisl. Mat. Mat. Fiz.
\yr 2018
\vol 58
\issue 5
\pages 852--856
\mathnet{http://mi.mathnet.ru/zvmmf10742}
\crossref{https://doi.org/10.7868/S0044466918050149}
\elib{https://elibrary.ru/item.asp?id=34914381}
\transl
\jour Comput. Math. Math. Phys.
\yr 2018
\vol 58
\issue 5
\pages 822--826
\crossref{https://doi.org/10.1134/S0965542518050123}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000435404100015}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85048616703}
Linking options:
  • https://www.mathnet.ru/eng/zvmmf10742
  • https://www.mathnet.ru/eng/zvmmf/v58/i5/p852
  • This publication is cited in the following 5 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:217
    References:33
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024