Ambrus, Gergely and Bárány, Imre and Grinberg, Victor (2016) Small subset sums. LINEAR ALGEBRA AND ITS APPLICATIONS, 499. pp. 6678. ISSN 00243795
Text
1_s2.0_S0024379516001580_main_u.pdf Restricted to Registered users only Download (363kB)  Request a copy 


Text
1502.04027.pdf Download (179kB)  Preview 
Official URL: http://dx.doi.org/10.1016/j.laa.2016.02.035
Abstract
Let ∥.∥ be a norm in ℝd whose unit ball is B. Assume that V ⊂ B is a finite set of cardinality n, with Σv ∈ Vv=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 ∥Σv ∈ Uv∥≤ ⌈d/2⌉. We also prove that this bound is sharp in general. We improve the estimate to O(√d) for the Euclidean and the max norms. An application on vector sums in the plane is also given. © 2016 Elsevier Inc. All rights reserved.
Item Type:  Article 

Additional Information:  N1 Funding Details: (DISCONV) 267165, ERC, European Research Council 
Uncontrolled Keywords:  Uranium; Vector sum; subset sum; K elements; Finite set; Euclidean; Cardinalities; Vector spaces; Vector sums; Steinitz theorem; NORMED SPACES 
Subjects:  Q Science / természettudomány > QA Mathematics / matematika Q Science / természettudomány > QA Mathematics / matematika > QA72 Algebra / algebra 
SWORD Depositor:  MTMT SWORD 
Depositing User:  MTMT SWORD 
Date Deposited:  04 Jan 2017 09:25 
Last Modified:  04 Jan 2017 09:25 
URI:  http://real.mtak.hu/id/eprint/44374 
Actions (login required)
Edit Item 