### Abstract

For an integer [various formulas omitted].
The quantity t(d) was introduced by Dash, Fukasawa, and Günlük, who showed that [various formulas omitted].
Using the Steinitz lemma, in a quantitative version due to Grinberg and Sevastyanov, we prove an upper bound of [various formulas omitted].
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 t(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.

Original language | English |
---|---|

Pages (from-to) | 323-335 |

Journal | Mathematical Programming |

Volume | 135 |

Issue number | 1-2 |

DOIs | |

Publication status | Published - 2012 |

## Fingerprint Dive into the research topics of 'Vectors in a box'. Together they form a unique fingerprint.

## Cite this

Buchin, K., Matousek, J., Moser, R. A., & Pálvölgyi, D. (2012). Vectors in a box.

*Mathematical Programming*,*135*(1-2), 323-335. https://doi.org/10.1007/s10107-011-0474-y