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., 2008, Volume 15, Number 6, Pages 11–19 (Mi da553)  

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

On polynomial solvability of some vector subset problems in Euclidean space with fixed dimension

E. Kh. Gimadiab, A. V. Pyatkinab, I. A. Rykovab

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

Abstract: Problems of choosing vectors in the multidimensional Euclidean space $\mathbb R^k$ are considered. The maximum norm of sum or the averaged square of the norm are considered as the problem objective. We present combinatorial algorithms with time complexity $O(k^2n^{2k})$. Thereby it is shown that the considered problems are polynomially solvable for fixed dimension of space $\mathbb R^k$. Bibl. 6.

Keywords: vector subset, Euclidean space, polynomial solvability.

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

English version:
Journal of Applied and Industrial Mathematics, 2010, 4:1, 48–53

Bibliographic databases:

UDC: 519.8
Received: 18.07.2008
Revised: 14.10.2008

Citation: E. Kh. Gimadi, A. V. Pyatkin, I. A. Rykov, “On polynomial solvability of some vector subset problems in Euclidean space with fixed dimension”, Diskretn. Anal. Issled. Oper., 15:6 (2008), 11–19; J. Appl. Industr. Math., 4:1 (2010), 48–53

Citation in format AMSBIB
\by E.~Kh.~Gimadi, A.~V.~Pyatkin, I.~A.~Rykov
\paper On polynomial solvability of some vector subset problems in Euclidean space with fixed dimension
\jour Diskretn. Anal. Issled. Oper.
\yr 2008
\vol 15
\issue 6
\pages 11--19
\jour J. Appl. Industr. Math.
\yr 2010
\vol 4
\issue 1
\pages 48--53

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. Pyatkin, “On the complexity of the maximum sum length vectors subset choice problem”, J. Appl. Industr. Math., 4:4 (2010), 549–552  mathnet  crossref  mathscinet  zmath  elib
    2. A. V. Dolgushev, A. V. Kel'manov, “An approximation algorithm for one problem of cluster analysis”, J. Appl. Industr. Math., 5:4 (2011), 551–558  mathnet  crossref  mathscinet  zmath
    3. A. V. Kelmanov, V. I. Khandeev, “A $2$-approximation polynomial algorithm for one clustering problem”, J. Appl. Industr. Math., 7:4 (2013), 515–521  mathnet  crossref  mathscinet
    4. E. Kh. Gimadi, I. A. Rykov, “A randomized algorithm for the vector subset problem with the maximal Euclidean norm of its sum”, J. Appl. Industr. Math., 9:3 (2015), 351–357  mathnet  crossref  crossref  mathscinet  elib
    5. 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
    6. 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
    7. A. V. Kel'manov, S. A. Khamidullin, V. I. Khandeev, “Fully polynomial-time approximation scheme for a sequence $2$-clustering problem”, J. Appl. Industr. Math., 10:2 (2016), 209–219  mathnet  crossref  crossref  mathscinet  elib
    8. 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
    9. 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
    10. V. V. Shenmaier, “An exact algorithm for finding a vector subset with the longest sum”, J. Appl. Industr. Math., 11:4 (2017), 584–593  mathnet  crossref  crossref  elib
    11. Kel'manov A. Khandeev V., “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
    12. Eremeev A.V. Kel'manov A.V. Pyatkin A.V., “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. Ignatov D. Khachay M. Labunets V. Loukachevitch N. Nikolenko S. Panchenko A. Savchenko A. Vorontsov K., Springer International Publishing Ag, 2017, 51–57  crossref  isi  scopus
    13. 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:453
    Full text:93
    First page:9

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