A Modified Greedy Algorithm for Submodular CoverEvent canceled

by Britta Peis (RWTH Aachen University)

Monday Jan 20, 2025, 6:15 PM → 7:15 PM Europe/Berlin

Arithmeum, Lennéstr., 2 - Seminarraum (Arithmeum / Research Institute for Discrete Mathematics)

Submodular cover is a common generalisation of set cover, integer cover, and the minimum weight spanning tree problem. In the submodular cover problem, we are given a submodular, nonnegative, and monotone non-decreasing function f defined on all subsets of a finite ground set E, and the task is to find a subset S satisfying f(S)=f(E) of minimum cost for some given cost function on E.

It is known that a naive greedy heuristic, which starts with the empty set, and iteratively adds elements of optimal ratio between cost andmarginal coverage has a performance ratio of of 1+ ln k, where k is the maximum f-value of a singleton (Wolsey 1982). This performance guarantee is nearly best possible, even in the special case of set cover (Feige 1996).

We propose and discuss a modification of the greedy algorithm where redundant elements are deleted in each iteration. We show that this modified greedy algorithm is guaranteed to terminate with an optimal solution to the submodular cover problem in case of submodular systems satisfying certain properties which are easily seen to be fulfilled by e.g. laminar set cover and matroid rank functions. 

(Joint work with Niklas Rieken and José Verschae.)

The Oberseminar takes place in the Seminarraum, 1^st floor. Participants are invited to have coffee or tea in the lounge before.