Journal article

Small subset sums

Let parallel to.parallel to be a norm in R-d whose unit ball is B. Assume that V subset of B is a finite set of cardinality n, with Sigma(v is an element of V) v = 0. We show that for every integer k with 0 <= k <= n, there exists a subset U of V consisting of k elements such that parallel to Sigma(v is an element of U) v parallel to <= inverted right perpendicular d/2 inverted left perpendicular. We also prove that this bound is sharp in general. We improve the estimate to O(root d) for the Euclidean and the max norms. An application on vector sums in the plane is also given. (C) 2016 Elsevier Inc. All rights reserved.


Related material