Upcoming Talks

Ist logo

Faster algorithms for integer programming using the Steinitz Lemma

Date: Friday, June 1, 2018 13:30 - 14:30
Speaker: Friedrich Eisenbrand (EPFL)
Location: Mondi Seminar Room 2, Central Building
Series: CS Talk Series
Host: Uli Wagner

Abstract:

Integer programming (IP) is concerned with the maximisation of a linear function, subject to linear and integrality constraints on the variables. IP is a fundamental NP-hard optimisation problem with a wide range of applications. In this talk, I will demonstrate how to apply a Lemma of Steinitz (1913) in order to speed up dynamic programming approaches to solve integer programming problems. We show that an integer program defined by $m$ equality constraints, in which each entry is integral bounded by $D$ in absolute value can be solved in time $(m D)^O(m)$ time. This improves upon the longstanding best bound of Papadimitriou (1981) of $(m D)^{O(m^2)}$. I will demonstrate the relevance of this result by improving or simplifying several recent results from the computer science and operations research literature. Joint work with Robert Weismantel ETH Zrich
Qr image
Download ICS Download invitation
Back to eventlist