Vectors in a boxReport as inadecuate

Vectors in a box - Download this document for free, or read online. Document in PDF available to download.

Mathematical Programming

, Volume 135, Issue 1–2, pp 323–335

First Online: 18 June 2011Received: 18 April 2010Accepted: 15 May 2011


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 with \{{\bf v} 1+{\bf v} 2+\cdots+{\bf v} t \in -1,1^d}\ , then there is a set \{S\subseteq \{1,2,\ldots,t\}}\ of indices, 2 ≤ |S| ≤ τd, such that \{\sum {i \in S}{\bf v} i \in -1,1^d}\ . The quantity τd was introduced by Dash, Fukasawa, and Günlük, who showed that τ2 = 2, τ3 = 4, and τd = Ω2, 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, 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. 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.

KeywordsSteinitz lemma Integer programming Master equality polyhedron Mathematics Subject Classification 200052B05 90C10  Download to read the full article text

Author: Kevin Buchin - Jiří Matoušek - Robin A. Moser - Dömötör Pálvölgyi


Related documents