Complexity of Integer Programming
Wednesday, August 10, 2016 - 2:00pm - 3:30pm
A landmark result on the complexity of integer programming by Lenstra in 1983 harnesses lattice basis reduction techniques to prove that, in constant dimension, integer linear programming can be solved in polynomial time. This algorithm also provides a fixed parameter tractable algorithm for mixed integer linear programming. We will cover Lenstra's algorithm from a modern perspective using Khinchine's flatness theorem, lattice theory of closest vector problem and shortest vector problem, and ellipsoid rounding. We will also discuss applications, improvements, and generalizations of these results.