## Abstract

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 language | English |
---|---|

Title of host publication | CiE 2018: Sailing Routes in the World of Computation |

Editors | Florin Manea, Russell G. Miller, Dirk Nowotka |

Number of pages | 8 |

Volume | 10936 LNCS |

Publisher | Springer, Cham |

Publication date | 30.07.2018 |

Pages | 89-96 |

ISBN (Print) | 978-3-319-94417-3 |

ISBN (Electronic) | 978-3-319-94418-0 |

DOIs | |

Publication status | Published - 30.07.2018 |

Event | 14th Conference on Computability in Europe - Kiel, Germany Duration: 30.07.2018 → 03.08.2018 Conference number: 216389 |