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.