Ambrus, Gergely and Bárány, Imre and Grinberg, Victor (2016) Small subset sums. LINEAR ALGEBRA AND ITS APPLICATIONS, 499. pp. 66-78. ISSN 0024-3795
![[img]](http://real.mtak.hu/style/images/fileicons/text.png) |
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: (DIS-CONV) 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 |
