RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor
Subscription

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


Diskretn. Anal. Issled. Oper., 2012, Volume 19, Number 2, Pages 92–100 (Mi da685)  

This article is cited in 14 scientific papers (total in 14 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
\Bibitem{She12}
\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
\mathnet{http://mi.mathnet.ru/da685}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2978615}
\transl
\jour J. Appl. Industr. Math.
\yr 2012
\vol 6
\issue 3
\pages 381--386
\crossref{https://doi.org/10.1134/S1990478912030131}


Linking options:
  • http://mi.mathnet.ru/eng/da685
  • http://mi.mathnet.ru/eng/da/v19/i2/p92

    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. 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
    13. Eremeev A.V. Kel'manov A.V. Kovalyov M.Y. Pyatkin A.V., “Maximum Diversity Problem With Squared Euclidean Distance”, Mathematical Optimization Theory and Operations Research, Lecture Notes in Computer Science, 11548, ed. Khachay M. Kochetov Y. Pardalos P., Springer International Publishing Ag, 2019, 541–551  crossref  zmath  isi  scopus
    14. Panasenko A., “a Ptas For One Cardinality-Weighted 2-Clustering Problem”, Mathematical Optimization Theory and Operations Research, Lecture Notes in Computer Science, 11548, ed. Khachay M. Kochetov Y. Pardalos P., Springer International Publishing Ag, 2019, 581–592  crossref  zmath  isi  scopus
  • ƒискретный анализ и исследование операций
    Number of views:
    This page:268
    Full text:67
    References:29
    First page:3

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