Loading...
research 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.
Type
research article
Web of Science ID
WOS:000374354600005
Authors
Publication date
2016
Publisher
Published in
Volume
499
Start page
66
End page
78
Peer reviewed
REVIEWED
EPFL units
Available on Infoscience
July 19, 2016
Use this identifier to reference this record