**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.