General information
Latest issue
Impact factor

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Diskretn. Anal. Issled. Oper.:

Personal entry:
Save password
Forgotten password?

Diskretn. Anal. Issled. Oper., 2015, Volume 22, Number 4, Pages 50–62 (Mi da824)  

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

An exact pseudopolynomial algorithm for a bi-partitioning problem

A. V. Kel'manovab, V. I. Khandeevb

a Novosibirsk State University, 2 Pirogov St., 630090 Novosibirsk, Russia
b Sobolev Institute of Mathematics, 4 Koptyug Ave., 630090 Novosibirsk, Russia

Abstract: We consider the strongly NP-hard problem of partitioning a set of Euclidean vectors into two sets (clusters) under the criterion of minimum sum-of-squared distances from the elements of clusters to their centers. The center of the first cluster is the average value of the vectors in the cluster, and the center of the second one is the origin. We prove that the problem is solvable in polynomial time in the case of fixed space dimension. We also present a pseudopolynomial algorithm which finds an optimal solution in the case of integer values of the components of the vectors in the input set and fixed space dimension. Bibliogr. 27.

Keywords: bi-partitioning, vector subset, squared Euclidean distances, NP-hardness, exact pseudopolynomial algorithm.


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

English version:
Journal of Applied and Industrial Mathematics, 2015, 9:4, 497–502

Bibliographic databases:

UDC: 519.16+519.85
Received: 16.09.2014
Revised: 22.02.2015

Citation: A. V. Kel'manov, V. I. Khandeev, “An exact pseudopolynomial algorithm for a bi-partitioning problem”, Diskretn. Anal. Issled. Oper., 22:4 (2015), 50–62; J. Appl. Industr. Math., 9:4 (2015), 497–502

Citation in format AMSBIB
\by A.~V.~Kel'manov, V.~I.~Khandeev
\paper An exact pseudopolynomial algorithm for a~bi-partitioning problem
\jour Diskretn. Anal. Issled. Oper.
\yr 2015
\vol 22
\issue 4
\pages 50--62
\jour J. Appl. Industr. Math.
\yr 2015
\vol 9
\issue 4
\pages 497--502

Linking options:

    SHARE: FaceBook Twitter Livejournal

    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, V. I. Khandeev, “Fully polynomial-time approximation scheme for a special case of a quadratic Euclidean 2-clustering problem”, Comput. Math. Math. Phys., 56:2 (2016), 334–341  mathnet  crossref  crossref  isi  elib
    2. 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
    3. A. V. Kel'manov, S. A. Khamidullin, V. I. Khandeev, “Exact pseudopolynomial algorithm for one sequence partitioning problem”, Autom. Remote Control, 78:1 (2017), 67–74  mathnet  crossref  isi  elib
    4. 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
    5. A. Kel'manov, V. Khandeev, “Some algorithms with guaranteed accuracy for 2-clustering problems with given center of one cluster”, 2017 International Multi-Conference on Engineering, Computer and Information Sciences (SIBIRCON), IEEE, 2017, 91–93  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), IEEE, 2017, 94–96  crossref  isi
    7. A. V. Eremeev, A. V. Kel'manov, A. V. Pyatkin, “On complexity of searching a subset of vectors with shortest average under a cardinality restriction”, Analysis of Images, Social Networks and Texts, AIST 2016, Communications in Computer and Information Science, 661, ed. D. Ignatov, M. Khachay, V. Labunets, N. Loukachevitch, S. Nikolenko, A. Panchenko, A. Savchenko, K. Vorontsov, Springler, 2017, 51–57  crossref  mathscinet  isi  scopus
    8. 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. van der Aalst, D. Ignatov, M. Khachay, S. Kuznetsov, V. Lempitsky, I. Lomazova, N. Loukachevitch, A. Napoli, A. Panchenko, P. Pardalos, A. Savchenko, S. Wasserman, Springer, 2018, 323–333  crossref  isi  scopus
  • Дискретный анализ и исследование операций
    Number of views:
    This page:177
    Full text:48
    First page:5

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