RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PERSONAL OFFICE
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., 2018, Volume 25, Number 4, Pages 131–148 (Mi da913)  

Approximability of the problem of finding a vector subset with the longest sum

V. V. Shenmaier

Sobolev Institute of Mathematics, 4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia

Abstract: We answer the question of existence of polynomial-time constant-factor approximation algorithms for the space of nonfixed dimension. We prove that, in Euclidean space the problem is solvable in polynomial time with accuracy $\sqrt\alpha$, where $\alpha=2/\pi$, and if $\mathrm P\neq\mathrm{NP}$ then there are no polynomial algorithms with better accuracy. It is shown that, in the case of the $\ell_p$ spaces, the problem is APX-complete if $p\in[1,2]$ and not approximable with constant accuracy if $\mathrm P\neq\mathrm{NP}$ and $p\in(2,\infty)$. Tab. 1, bibliogr. 21.

Keywords: sum vector, search for a vector subset, approximation algorithm, inapproximability bound.

Funding Agency Grant Number
Russian Science Foundation 16-11-10041
The author was supported by the Russian Science Foundation (project no. 16-11-10041).


DOI: https://doi.org/10.17377/daio.2018.25.618

Full text: PDF file (373 kB)
First page: PDF file
References: PDF file   HTML file

English version:
Journal of Applied and Industrial Mathematics, 2018, 12:4, 749–758

Document Type: Article
UDC: 519.16
Received: 11.04.2018
Revised: 13.07.2018

Citation: V. V. Shenmaier, “Approximability of the problem of finding a vector subset with the longest sum”, Diskretn. Anal. Issled. Oper., 25:4 (2018), 131–148; J. Appl. Industr. Math., 12:4 (2018), 749–758

Citation in format AMSBIB
\Bibitem{She18}
\by V.~V.~Shenmaier
\paper Approximability of the problem of finding a~vector subset with the longest sum
\jour Diskretn. Anal. Issled. Oper.
\yr 2018
\vol 25
\issue 4
\pages 131--148
\mathnet{http://mi.mathnet.ru/da913}
\crossref{https://doi.org/10.17377/daio.2018.25.618}
\transl
\jour J. Appl. Industr. Math.
\yr 2018
\vol 12
\issue 4
\pages 749--758
\crossref{https://doi.org/10.1134/S1990478918040154}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85058077896}


Linking options:
  • http://mi.mathnet.ru/eng/da913
  • http://mi.mathnet.ru/eng/da/v25/i4/p131

    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
  • Дискретный анализ и исследование операций
    Number of views:
    This page:10
    References:4

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