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, 2018, Volume 24, Number 4, Pages 189–198
DOI: https://doi.org/10.21538/0134-4889-2018-24-4-189-198 (Mi timm1585) 		 
This article is cited in 3 scientific papers (total in 3 papers)

On the Complexity of Some Max–Min Clustering Problems

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

a Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk
b Novosibirsk State University
Full-text PDF (193 kB) Citations (3)
References:
PDF
HTML
DOI: https://doi.org/10.21538/0134-4889-2018-24-4-189-198
Abstract: Two similar problems of searching for a family of disjoint subsets (clusters) in a finite set of points in Euclidean space are considered. In these problems, the size of the smallest cluster should be maximized so that in each cluster the intracluster quadratic variation of the points with respect to the center of the cluster would not exceed a given (constant) fraction of the total quadratic variation of the points of the input set with respect to its centroid. In the first problem, the centers of intracluster variations are arbitrary points of the space given at the input. In the second problem, the centers of the intracluster variation are unknown (to be found) but must lie in the input set. Both problems are proved to be NP-hard even on the real line both in the general case when the number of the clusters is a part of the input and in the parametric case when the number of the clusters is fixed.
Keywords: Euclidean space, clustering, max–min problem, quadratic variation, NP-hardness.
Funding agency Grant number
Russian Science Foundation 16-11-10041
This work was supported by the Russian Science Foundation (project no. 16-11-10041).
Received: 30.07.2018
Revised: 08.10.2018
Accepted: 12.11.2018
English version:
Proceedings of the Steklov Institute of Mathematics (Supplementary issues), 2020, Volume 309, Issue 1, Pages S65–S73
DOI: https://doi.org/10.1134/S0081543820040082
Bibliographic databases:
Document Type: Article
UDC: 519.16+519.85
MSC: 68W25, 68Q25
Language: Russian
Citation: A. V. Kel'manov, A. V. Pyatkin, V. I. Khandeev, “On the Complexity of Some Max–Min Clustering Problems”, Trudy Inst. Mat. i Mekh. UrO RAN, 24, no. 4, 2018, 189–198; Proc. Steklov Inst. Math. (Suppl.), 309, suppl. 1 (2020), S65–S73
Citation in format AMSBIB
\Bibitem{KelPyaKha18}
\by A.~V.~Kel'manov, A.~V.~Pyatkin, V.~I.~Khandeev
\paper On the Complexity of Some Max--Min Clustering Problems
\serial Trudy Inst. Mat. i Mekh. UrO RAN
\yr 2018
\vol 24
\issue 4
\pages 189--198
\mathnet{http://mi.mathnet.ru/timm1585}
\crossref{https://doi.org/10.21538/0134-4889-2018-24-4-189-198}
\elib{https://elibrary.ru/item.asp?id=36517709}
\transl
\jour Proc. Steklov Inst. Math. (Suppl.)
\yr 2020
\vol 309
\issue , suppl. 1
\pages S65--S73
\crossref{https://doi.org/10.1134/S0081543820040082}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000464575200014}
Linking options:
  • https://www.mathnet.ru/eng/timm1585
  • https://www.mathnet.ru/eng/timm/v24/i4/p189
    • This publication is cited in the following 3 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:190
    Full-text PDF :51
    References:36
    First page:2
     
      Contact us:
    		  Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024