Seminar: Britta Peis (RWTH Aachen University), International speaker

We present a general approximation framework for weighted integer covering problems. In a weighted integer covering problem, the goal is to determine a non-negative integer solution x to  system Ax ≥ r minimizing a non-negative linear cost function c. We analyze the performance of two commonly used primal-dual algorithms (greedy dual and dual fitting) on some restricted systems (A, r) that we call greedy systems. We also study the impact of truncation, i.e. a scheme for improving the IP formulation of the problem. (Joint work with Jose Verschae, Niklas Rieken, and Andreas Wierz.)