Article ID Journal Published Year Pages File Type
4647780 Discrete Mathematics 2013 4 Pages PDF
Abstract
Given a rational a=p/q and N nonnegative d-dimensional real vectors u1,…,uN, 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)(u1+⋯+uN). 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.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,