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


Zh. Vychisl. Mat. Mat. Fiz., 2016, Volume 56, Number 3, Pages 498–504 (Mi zvmmf10352)  

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

On the complexity of some quadratic Euclidean 2-clustering problems

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

a Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk
b Novosibirsk State University

Abstract: Some problems of partitioning a finite set of points of Euclidean space into two clusters are considered. In these problems, the following criteria are minimized: (1) the sum over both clusters of the sums of squared pairwise distances between the elements of the cluster and (2) the sum of the (multiplied by the cardinalities of the clusters) sums of squared distances from the elements of the cluster to its geometric center, where the geometric center (or centroid) of a cluster is defined as the mean value of the elements in that cluster. Additionally, another problem close to (2) is considered, where the desired center of one of the clusters is given as input, while the center of the other cluster is unknown (is the variable to be optimized) as in problem (2). Two variants of the problems are analyzed, in which the cardinalities of the clusters are (1) parts of the input or (2) optimization variables. It is proved that all the considered problems are strongly NP-hard and that, in general, there is no fully polynomial-time approximation scheme for them (unless P = NP).

Funding Agency Grant Number
Russian Foundation for Basic Research 15-01-00462_а
15-01-00976_а
16-07-00168_а


DOI: https://doi.org/10.7868/S0044466916030091

Full text: PDF file (158 kB)
References: PDF file   HTML file

English version:
Computational Mathematics and Mathematical Physics, 2016, 56:3, 491–497

UDC: 519.7
Received: 07.04.2015

Citation: A. V. Kel'manov, A. V. Pyatkin, “On the complexity of some quadratic Euclidean 2-clustering problems”, Zh. Vychisl. Mat. Mat. Fiz., 56:3 (2016), 498–504; Comput. Math. Math. Phys., 56:3 (2016), 491–497

Citation in format AMSBIB
\Bibitem{KelPya16}
\by A.~V.~Kel'manov, A.~V.~Pyatkin
\paper On the complexity of some quadratic Euclidean 2-clustering problems
\jour Zh. Vychisl. Mat. Mat. Fiz.
\yr 2016
\vol 56
\issue 3
\pages 498--504
\mathnet{http://mi.mathnet.ru/zvmmf10352}
\crossref{https://doi.org/10.7868/S0044466916030091}
\elib{http://elibrary.ru/item.asp?id=25678781}
\transl
\jour Comput. Math. Math. Phys.
\yr 2016
\vol 56
\issue 3
\pages 491--497


Linking options:
  • http://mi.mathnet.ru/eng/zvmmf10352
  • http://mi.mathnet.ru/eng/zvmmf/v56/i3/p498

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. A. V. Kel'manov, A. V. Motkova, “Exact pseudopolinomial algorithms for a balanced $2$-clustering problem”, J. Appl. Industr. Math., 10:3 (2016), 349–355  mathnet  crossref  crossref  mathscinet  elib
    2. A. Kel'manov, A. Motkova, “A fully polynomial-time approximation scheme for a special case of a balanced 2-clustering problem”, Discrete Optimization and Operations Research, Lecture Notes in Computer Science, 9869, eds. Y. Kochetov, M. Khachay, V. Beresnev, E. Nurminski, P. Pardalos, Springer Int Publishing Ag, 2016, 182–192  crossref  mathscinet  zmath  isi  scopus
    3. A. V. Kel'manov, A. V. Motkova, V. V. Shenmaier, “Approximation scheme for the problem of weighted 2-partitioning with a fixed center of one cluster”, Proc. Steklov Inst. Math. (Suppl.), 303, suppl. 1 (2018), 136–145  mathnet  crossref  crossref  isi  elib
    4. A. Pyatkin, D. Aloise, N. Mladenovic, “NP-hardness of balanced minimum sum-of-squares clustering”, Pattern Recognit. Lett., 97 (2017), 44–45  crossref  isi
    5. A. Kel'manov, “Efficient approximation algorithms for some NP-hard problems of partitioning a set and a sequence”, 2017 International Multi-Conference on Engineering, Computer and Information Sciences, SIBIRCON 2017, IEEE, 2017, 87–90  crossref  isi
    6. A. Kel'manov, A. Motkova, “An approximation polynomial-time algorithm for a cardinality-weighted 2-clustering problem”, 2017 International Multi-Conference on Engineering, Computer and Information Sciences, SIBIRCON 2017, IEEE, 2017, 94–96  crossref  isi
    7. A. Kel'manov, A. Motkova, V. Shenmaier, “An approximation scheme for a weighted two-cluster partition problem”, Analysis of Images, Social Networks and Texts, AIST 2017, Lecture Notes in Computer Science, 10716, eds. W. VanDerAalst, D. Ignatov, M. Khachay, S. Kuznetsov, V. Lempitsky, I. Lomazova, N. Loukachevitch, Springer, 2018, 323–333  crossref  isi  scopus
    8. A. V. Kel'manov, A. V. Panasenko, V. I. Khandeev, “Exact algorithms of searching for the largest size cluster in two integer 2-clustering problems”, Num. Anal. Appl., 12:2 (2019), 105–115  mathnet  crossref  crossref  isi  elib
  • Журнал вычислительной математики и математической физики Computational Mathematics and Mathematical Physics
    Number of views:
    This page:141
    Full text:10
    References:36
    First page:10

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020