Using Structural Properties for Integer Programs

Integer programs (IPs) are one of the fundamental tools used to solve combinatorial problems in theory and practice. Understanding the structure of solutions of IPs is thus helpful to argue about the existence of solutions with a certain simple structure, leading to significant algorithmic improvements. Typical examples for such structural properties are solutions that use a specific type of variable very often or solutions that only contain few non-zero variables. The last decade has shown the usefulness of this method. In this paper we summarize recent progress for structural properties and their algorithmic implications in the area of approximation algorithms and fixed parameter tractability. Concretely, we show how these structural properties lead to optimal approximation algorithms for the classical MAKESPAN SCHEDULING scheduling problem and to exact polynomial-time algorithm for the BIN PACKING problem with a constant number of different item sizes.