Vectors in a box
OPEN ACCESS
Loading...
Author / Producer
Date
2012-10
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
For an integer d ≥ 1, let τ(d) be the smallest integer with the following property: if v 1, v 2, . . . , v t is a sequence of t ≥ 2 vectors in [−1, 1]d with 𝐯�1+𝐯�2+⋯+𝐯�𝑡�∈[−1,1]𝑑� , then there is a set 𝑆�⊆{1,2,…,𝑡�} of indices, 2 ≤ |S| ≤ τ(d), such that ∑𝑖�∈𝑆�𝐯�𝑖�∈[−1,1]𝑑� . The quantity τ(d) was introduced by Dash, Fukasawa, and Günlük, who showed that τ(2) = 2, τ(3) = 4, and τ(d) = Ω(2d), and asked whether τ(d) is finite for all d. Using the Steinitz lemma, in a quantitative version due to Grinberg and Sevastyanov, we prove an upper bound of τ(d) ≤ d d+o(d), and based on a construction of Alon and Vũ, whose main idea goes back to Håstad, we obtain a lower bound of τ(d) ≥ d d/2-o(d). These results contribute to understanding the master equality polyhedron with multiple rows defined by Dash et al. which is a “universal” polyhedron encoding valid cutting planes for integer programs (this line of research was started by Gomory in the late 1960s). In particular, the upper bound on τ(d) implies a pseudo-polynomial running time for an algorithm of Dash et al. for integer programming with a fixed number of constraints. The algorithm consists in solving a linear program, and it provides an alternative to a 1981 dynamic programming algorithm of Papadimitriou.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
135 (1-2)
Pages / Article No.
323 - 335
Publisher
Springer
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Steinitz lemma; Integer programming; Master equality polyhedron; 52B05; 90C10
Organisational unit
03457 - Welzl, Emo (emeritus) / Welzl, Emo (emeritus)