Abstrakt
For an integer d a parts per thousand yen 1, let tau(d) be the smallest integer with the following property: if v (1), v (2), . . . , v (t) is a sequence of t a parts per thousand yen 2 vectors in [-1, 1] (d) with , then there is a set of indices, 2 a parts per thousand currency sign |S| a parts per thousand currency sign tau(d), such that. The quantity tau(d) was introduced by Dash, Fukasawa, and Gunluk, who showed that tau(2) = 2, tau(3) = 4, and tau(d) = Omega(2 (d) ), and asked whether tau(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 tau(d) a parts per thousand currency sign d (d+o(d)), and based on a construction of Alon and V, whose main idea goes back to HAyenstad, we obtain a lower bound of tau(d) a parts per thousand yen 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 tau(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.