### ?

## Finding a subset of nonnegative vectors with a coordinatewise large sum

Discrete Mathematics. 2013. Vol. 313. No. 5. P. 622-625.

Bogdanov I., Chelnokov G. R.

Given a rational $a = p/q$ and $N$ nonnegative $d$-dimensional real vectors $u_1, \dots , u_N$ , we

show that it is always possible to choose $(d − 1) + \lceil(pN − d + 1)/q\rceil$ of them such that

their sum is (componentwise) at least $(p/q)(u_1 + \cdots + u_N )$. For fixed $d$ and $a$, this bound

is sharp if $N$ is large enough. The method of the proof uses Carathйodory’s theorem from

linear programming.

Language:
English