A randomized algorithm for finding a subset of vectors with the maximum Euclidean norm of their sum
Edward Kh. Gimadi, Ivan A. Rykov · Journal of Applied and Industrial Mathematics · 2015
We present a randomized approximation algorithm for the problem of finding a subset of a finite vector set in the Euclidean space with the maximal norm of the sum vector. We show that, with an appropriate choice of parameters, the algorithm is polynomial for the problem with every fixed dimension and asymptotically optimal.