REAL

Small subset sums

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] Text
1_s2.0_S0024379516001580_main_u.pdf
Restricted to Registered users only

Download (354Kb) | Request a copy
[img]
Preview
Text
1502.04027.pdf

Download (175Kb) | Preview

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)

View Item View Item