Finding a subset of nonnegative vectors with a coordinatewise large sum

Ilya I. Bogdanov; Grigory R. Chelnokov

doi:10.1016/j.disc.2012.12.006

paper

Finding a subset of nonnegative vectors with a coordinatewise large sum

arXiv:1201.2880 · doi:10.1016/j.disc.2012.12.006

Abstract

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) + ⌈(pN - d + 1) / q ⌉$ of them such that their sum is (componentwise) at least $(p / q) (u_{1} + ... + 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.