Using structural properties for integer programs

Sebastian Berndt*, Kim Manuel Klein

*Corresponding author for this work


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.

Original languageEnglish
Title of host publicationCiE 2018: Sailing Routes in the World of Computation
EditorsFlorin Manea, Russell G. Miller, Dirk Nowotka
Number of pages8
Volume10936 LNCS
PublisherSpringer, Cham
Publication date30.07.2018
ISBN (Print)978-3-319-94417-3
ISBN (Electronic)978-3-319-94418-0
Publication statusPublished - 30.07.2018
Event14th Conference on Computability in Europe - Kiel, Germany
Duration: 30.07.201803.08.2018
Conference number: 216389


Dive into the research topics of 'Using structural properties for integer programs'. Together they form a unique fingerprint.

Cite this