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
Year:
2016
Publisher:
New York, Elsevier Science Inc
ISSN:
0024-3795
Keywords:
Laboratories:




 Record created 2016-07-19, last modified 2018-12-03


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)