##
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.

Published in:

Linear Algebra And Its Applications, 499, 66-78

Publisher:

New York, Elsevier Science Inc

ISSN:

0024-3795

Keywords:

Laboratories:

Record created 2016-07-19, last modified 2018-01-28