Vectors in a box

K. Buchin, J. Matousek, R.A. Moser, D. Pálvölgyi

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

3 Citaten (Scopus)


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.
Originele taal-2Engels
Pagina's (van-tot)323-335
TijdschriftMathematical Programming
Nummer van het tijdschrift1-2
StatusGepubliceerd - 2012


Duik in de onderzoeksthema's van 'Vectors in a box'. Samen vormen ze een unieke vingerafdruk.

Citeer dit