BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//CERN//INDICO//EN
BEGIN:VEVENT
SUMMARY:A Modified Greedy Algorithm for Submodular Cover [Event canceled]
DTSTART:20250120T171500Z
DTEND:20250120T181500Z
DTSTAMP:20260613T223800Z
UID:indico-event-139@math-events.uni-bonn.de
DESCRIPTION:Speakers: Britta Peis (RWTH Aachen University)\n\nSubmodular c
 over is a common generalisation of set cover\, integer cover\, and the m
 inimum weight spanning tree problem. In the submodular cover problem\, we
  are given a submodular\, nonnegative\, and monotone non-decreasing func
 tion 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.\nIt is known that a naive greedy heuristic\, which sta
 rts 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 perfor
 mance guarantee is nearly best possible\, even in the special case of set 
 cover (Feige 1996).\nWe 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 o
 ptimal solution to the submodular cover problem in case of submodular syst
 ems satisfying certain properties which are easily seen to be fulfilled by
  e.g. laminar set cover and matroid rank functions. \n(Joint work with
  Niklas Rieken and José Verschae.)\nThe Oberseminar takes place in the 
 Seminarraum\, 1st floor. Participants are invited to have coffee or tea in
  the lounge before.\n\nhttps://math-events.uni-bonn.de/event/139/
LOCATION:Arithmeum\, Lennéstr.\,  2 - Seminarraum (Arithmeum / Research I
 nstitute for Discrete Mathematics)
URL:https://math-events.uni-bonn.de/event/139/
END:VEVENT
END:VCALENDAR