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., 2012, Volume 19, Number 2, Pages 92–100 (Mi da685)  

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

Approximation scheme for one problem of a vector subset choice

V. V. Shenmaier

S. L. Sobolev Institute of Mathematics, SB RAS, Novosibirsk, Russia

Abstract: We consider the following clustering problem: in a given vector set to find a vector subset of cardinality $k$ with the minimal quadratic deviation from its mean. The distances between vectors are defined by the Euclidean metric. We propose an approximation scheme (PTAS) that solves this problem with an arbitrary relative error $\varepsilon$ in time $O(n^{2/\varepsilon+1}(9/\varepsilon)^{3/\varepsilon d})$, where $n$ is the number of vectors in the original set and $d$ is the space dimension. Ill. 1, bibliogr. 4.

Keywords: vector subset choice, cluster analysis, approximation scheme, approximation algorithm.

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

English version:
Journal of Applied and Industrial Mathematics, 2012, 6:3, 381–386

Bibliographic databases:

UDC: 519.176
Received: 15.06.2011
Revised: 08.09.2011

Citation: V. V. Shenmaier, “Approximation scheme for one problem of a vector subset choice”, Diskretn. Anal. Issled. Oper., 19:2 (2012), 92–100; J. Appl. Industr. Math., 6:3 (2012), 381–386

Citation in format AMSBIB
\by V.~V.~Shenmaier
\paper Approximation scheme for one problem of a~vector subset choice
\jour Diskretn. Anal. Issled. Oper.
\yr 2012
\vol 19
\issue 2
\pages 92--100
\jour J. Appl. Industr. Math.
\yr 2012
\vol 6
\issue 3
\pages 381--386

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. Kelmanov, S. M. Romanchenko, S. A. Khamidullin, “Tochnye psevdopolinomialnye algoritmy dlya nekotorykh trudnoreshaemykh zadach poiska podposledovatelnosti vektorov”, Zh. vychisl. matem. i matem. fiz., 53:1 (2013), 143–153  mathnet  crossref  elib
    2. A. E. Galashov, A. V. Kel'manov, “A $2$-approximate algorithm to solve one problem of the family of disjoint vector subsets”, Autom. Remote Control, 75:4 (2014), 595–606  mathnet  crossref  isi
    3. A. V. Kel'manov, S. M. Romanchenko, “FPTAS for solving a problem of search for a vector subset”, J. Appl. Industr. Math., 8:3 (2014), 329–336  mathnet  crossref  mathscinet
    4. A. V. Dolgushev, A. V. Kel'manov, V. V. Shenmaier, “Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters”, Proc. Steklov Inst. Math. (Suppl.), 295, suppl. 1 (2016), 47–56  mathnet  crossref  mathscinet  isi  elib
    5. V. V. Shenmaier, “Solving some vector subset problems by Voronoi diagrams”, J. Appl. Industr. Math., 10:4 (2016), 560–566  mathnet  crossref  crossref  mathscinet  elib
    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
    7. 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
    8. A. V. Kelmanov, S. M. Romanchenko, S. A. Khamidullin, “An approximation scheme for a problem of finding a subsequence”, Num. Anal. Appl., 10:4 (2017), 313–323  mathnet  crossref  crossref  isi  elib
    9. A. Ageev, A. Kel'manov, A. Pyatkin, S. Khamidullin, V. Shenmaier, “1/2-approximation polynomial-time algorithm for a problem of searching a subset”, 2017 International Multi-Conference on Engineering, Computer and Information Sciences (SIBIRCON), IEEE, 2017, 8–12  crossref  isi
    10. 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), IEEE, 2017, 87–90  crossref  isi
    11. 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
    12. Kel'manov A. Motkova A. Shenmaier V., “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, ed. VanDerAalst W. Ignatov D. Khachay M. Kuznetsov S. Lempitsky V. Lomazova I. Loukachevitch N. Napoli A. Panchenko A. Pardalos P. Savchenko A. Wasserman S., Springer International Publishing Ag, 2018, 323–333  crossref  isi  scopus
  • ƒискретный анализ и исследование операций
    Number of views:
    This page:260
    Full text:64
    First page:3

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