General information
Latest issue
Impact factor
Guidelines for authors
Submit a manuscript

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Avtomat. i Telemekh.:

Personal entry:
Save password
Forgotten password?

Avtomat. i Telemekh., 2014, Issue 4, Pages 5–19 (Mi at7528)  

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

Mathematical programming problems

$2$-approximate algorithm to solve one problem of the family of disjoint vector subsets

A. E. Galashova, A. V. Kel'manovb

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

Abstract: Consideration was given to the problem of seeking a family of disjoint subsets of given cardinalities in a finite set of Euclidean space vectors. The minimal sum of the squared distances from the subset elements to their centers was used as the search criterion. The subset centers are optimizable variables defined as the mean values over the elements of the required subsets. The problem was shown to be NP-hard in the strong sense. To solve it, a $2$-approximate algorithm was proposed which is polynomial for a fixed number of the desired subsets.

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

English version:
Automation and Remote Control, 2014, 75:4, 595–606

Bibliographic databases:

Presented by the member of Editorial Board: . . 

Received: 14.11.2013

Citation: A. E. Galashov, A. V. Kel'manov, “A $2$-approximate algorithm to solve one problem of the family of disjoint vector subsets”, Avtomat. i Telemekh., 2014, no. 4, 5–19; Autom. Remote Control, 75:4 (2014), 595–606

Citation in format AMSBIB
\by A.~E.~Galashov, A.~V.~Kel'manov
\paper A~$2$-approximate algorithm to solve one problem of the family of disjoint vector subsets
\jour Avtomat. i Telemekh.
\yr 2014
\issue 4
\pages 5--19
\jour Autom. Remote Control
\yr 2014
\vol 75
\issue 4
\pages 595--606

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. E. Kh. Gimadi, A. V. Kel'manov, A. V. Pyatkin, M. Yu. Khachai, “Efficient algorithms with performance estimates for some problems of finding several cliques in a complete undirected weighted graph”, Proc. Steklov Inst. Math. (Suppl.), 289, suppl. 1 (2015), 88–101  mathnet  crossref  mathscinet  isi  elib
    2. A. V. Kel'manov, V. I. Khandeev, “A randomized algorithm for two-cluster partition of a set of vectors”, Comput. Math. Math. Phys., 55:2 (2015), 330–339  mathnet  crossref  crossref  mathscinet  isi  elib  elib
    3. A. V. Kel'manov, V. I. Khandeev, “An exact pseudopolynomial algorithm for a bi-partitioning problem”, J. Appl. Industr. Math., 9:4 (2015), 497–502  mathnet  crossref  crossref  mathscinet  elib
    4. O. A. Zverkov, A. V. Seliverstov, V. A. Lyubetsky, “A database of plastid protein families from red algae and apicomplexa and expression regulation of the moeb gene”, Biomed Res. Int., 2015, 510598  crossref  isi  scopus
    5. L. I. Rubanov, A. V. Seliverstov, O. A. Zverkov, V. A. Lyubetsky, “A method for identification of highly conserved elements and evolutionary analysis of superphylum alveolata”, BMC Bioinformatics, 17 (2016), 385  crossref  isi  elib  scopus
    6. A. E. Galashov, A. V. Kel'manov, “On pseudopolynomial-time solvability of a quadratic Euclidean problem of finding a family of disjoint subsets”, Num. Anal. Appl., 10:1 (2017), 11–16  mathnet  crossref  crossref  mathscinet  isi  elib
  • Avtomatika i Telemekhanika
    Number of views:
    This page:217
    Full text:26
    First page:36

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