Diskretnyi Analiz i Issledovanie Operatsii
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor
Guidelines for authors

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS


Diskretn. Anal. Issled. Oper.:
Year:
Volume:
Issue:
Page:
Find




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

Diskretnyi Analiz i Issledovanie Operatsii, 2024, Volume 31, Issue 2, Pages 136–143
DOI: https://doi.org/10.33048/daio.2024.31.787 (Mi da1349) 		 
On the complexity of the problem of choice of large clusters

A. V. Pyatkin

Sobolev Institute of Mathematics, 4 Acad. Koptyug Avenue, 630090 Novosibirsk, Russia
Full-text PDF (325 kB) First page
References:
PDF
HTML
DOI: https://doi.org/10.33048/daio.2024.31.787
Abstract: The paper considers the following problem. Given a set of Euclidean vectors, find several clusters with a restriction on the maximum scatter of each cluster so that the size of the minimum cluster would be maximum. Here the scatter is the sum of squared distances from the cluster elements to its centroid. The NP-hardness of this problem is proved in the case where the dimension of the space is a part of the input. Bibliogr. 15.
Keywords: cluster, centroid, scatter, NP-hardness.
Funding agency Grant number
Ministry of Science and Higher Education of the Russian Federation FWNF–2022–0019
Received: 08.11.2023
Revised: 20.11.2023
Accepted: 22.12.2023
English version:
Journal of Applied and Industrial Mathematics, 2024, Volume 18, Issue 2, Pages 312–315
DOI: https://doi.org/10.1134/S1990478924020121
Document Type: Article
UDC: 519.8+518.25
Language: Russian
Citation: A. V. Pyatkin, “On the complexity of the problem of choice of large clusters”, Diskretn. Anal. Issled. Oper., 31:2 (2024), 136–143; J. Appl. Industr. Math., 18:2 (2024), 312–315
Citation in format AMSBIB
\Bibitem{Pya24}
\by A.~V.~Pyatkin
\paper On the complexity of the problem of~choice~of~large~clusters
\jour Diskretn. Anal. Issled. Oper.
\yr 2024
\vol 31
\issue 2
\pages 136--143
\mathnet{http://mi.mathnet.ru/da1349}
\crossref{https://doi.org/10.33048/daio.2024.31.787}
\transl
\jour J. Appl. Industr. Math.
\yr 2024
\vol 18
\issue 2
\pages 312--315
\crossref{https://doi.org/10.1134/S1990478924020121}
Linking options:
  • https://www.mathnet.ru/eng/da1349
  • https://www.mathnet.ru/eng/da/v31/i2/p136
    • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Дискретный анализ и исследование операций
     
      Contact us:
    		  Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024