Finding a subset of nonnegative vectors with a coordinatewise large sum

Ilya I. Bogdanov, Grigory R. Chelnokov

Given a rational $a=p/q$ and $N$ nonnegative $d$-dimensional real vectors $u_1$, ..., $u_N$, we show that it is always possible to choose $(d-1)+\lceil (pN-d+1)/q\rceil$ of them su…