Complexity and Approximation of Finding the Longest Vector Sum
Autor: | V. V. Shenmaier |
---|---|
Rok vydání: | 2018 |
Předmět: | |
Zdroj: | Computational Mathematics and Mathematical Physics. 58:850-857 |
ISSN: | 1555-6662 0965-5425 |
Popis: | The problem under study is, given a finite set of vectors in a normed vector space, find a subset which maximizes the norm of the vector sum. For each $${{\ell }_{p}}$$ norm, $$p \in [1,\infty )$$ , the problem is proved to have an inapproximability bound in the class of polynomial-time algorithms. For an arbitrary normed space of dimension $$O(logn)$$ , a randomized polynomial-time approximation scheme is proposed. |
Databáze: | OpenAIRE |
Externí odkaz: |