The Dutch Seminar on Optimization is an initiative to bring together researchers from the Netherlands and beyond, with topics that are centered around Optimization in a broad sense. We would like to invite all researchers, especially also PhD students, who are working on related topics to join the events.
Speaker: Britta Peis (RWTH Aachen)
Title:
Primal-dual approximation framework for weighted integer covering problems.
Abstract:
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.)
The lecture will be given online. Please visit the website for more information and the zoom link.