Date & Time: Tuesday, March 11, 2014, 13:45-14:45.
Venue: Ramanujan Hall

Title: Randomized Algorithms for Set Covering Problems in Hypergraphs

Speaker: Anand Srivastav, University of Kiel

Abstract: In this talk we consider different covering problems in hypergraphs, like {\sc set cover} and {\sc $b$-multisetcover}. As both problems are NP-hard, the aim is to find polynomial-time algorithms approximating the optimum as tight as possible. We present randomized algorithms of hybrid type, where the randomization step is followed by a repairing step, if the solution is infeasible. Such an approach is very common in practice, but the mathematical challenge is to analyse these procedures simultaneously as the repairing depends on the randomized generation of a candidate solution. The analysis is accomplished with concentration bounds, among them the Azuma-Hoeffding martingale inequality, leading to the solution of an open problem arising from the work of Peleg, Schechtman and Wool (1997) for {\sc $b$-multisetcover}, and to the presently best approximations for both problems.