Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, February 27, 2020, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Christoph Grunau
We design a Local Computation Algorithm (LCA) for the set cover problem. Given a set system where each set has size at most s, the algorithm reports whether a given set is in some fixed set cover whose expected size is O(log s) times the minimum fractional set cover value. The algorithm is based on a parallel set cover algorithm that admits an efficient simulation in the LCA model by using a sparsification technique introduced in [Ghaffari and Uitto, SODA'19] for the maximal independent set problem. This is joint work with Slobodan Mitrović, Ronitt Rubinfeld and Ali Vakilian.
Automatic MiSe System Software Version 1.4803M | admin login