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

 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)
References: PDF file   HTML file

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

UDC: 519.16
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} \elib{http://elibrary.ru/item.asp?id=36449715} \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}