Approximability of the Problem of Finding a Vector Subset with the Longest Sum
- 作者: Shenmaier V.1
-
隶属关系:
- Sobolev Institute of Mathematics
- 期: 卷 12, 编号 4 (2018)
- 页面: 749-758
- 栏目: Article
- URL: https://journals.rcsi.science/1990-4789/article/view/213133
- DOI: https://doi.org/10.1134/S1990478918040154
- ID: 213133
如何引用文章
详细
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 a \), where α = 2/π, and if P ≠ NP then there are no polynomial algorithms with better accuracy. It is shown that, in the case of the ℓp spaces, the problem is APX-complete if p ∈ [1, 2] and not approximable with constant accuracy if P ≠ NP and p ∈ (2,∞).
作者简介
V. Shenmaier
Sobolev Institute of Mathematics
编辑信件的主要联系方式.
Email: shenmaier@mail.ru
俄罗斯联邦, pr. Akad. Koptyuga 4, Novosibirsk, 630090