Complexity and Approximation of Finding the Longest Vector Sum

Autor:	V. V. Shenmaier
Rok vydání:	2018
Předmět:	Combinatorics Computational Mathematics 020303 mechanical engineering & transports 0203 mechanical engineering 010201 computation theory & mathematics 0102 computer and information sciences 02 engineering and technology 01 natural sciences Finite set Mathematics Normed vector space
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:	https://explore.openaire.eu/search/publication?articleId=doi_________::6fe831ddcde93b1072b3453ff1a4b251 https://doi.org/10.1134/s0965542518060131 Zobrazit plný text záznamu Full text from SpringerLink