Preemptive Min Sum Set Cover and Minimum Latency Submodular Cover
Ruben van der Zwaan

The talk is based on joint work with Sungjin Im, Viswanath Nagarajanand Maxim 
Sviridenko.  In this talk I give a gentle introduction and examples of why the 
problems are interesting. There are no proofs, only the intuition behind the 
proofs for Preemptive Min Sum Cover and a broad outline of the Minimum Latency 
Submodular Cover algorithm.

Preemptive Min Sum Set Cover:
In the (non-preemptive) Generalized Min Sum Set Cover Problem, we are given n 
ground elements and a collection of subsets S1, ..., Sm of the ground set. Each 
set S has a positive requirement k(S) that has to be fulfilled. We would like 
to order all elements of the ground set to minimize the total (weighted) cover 
time of all sets. The cover time of a set S is defined as the first index j in 
the ordering such that the first j elements in the ordering contain k(S) 
elements in S. This problem was introduced by Azar, Gamzu, Yin (2009) with 
interesting motivations in web page ranking and broadcast scheduling. For this 
problem, constant approximations are known due to Bansal, Gupta, Krishnaswamy 
(2010) (factor 485) and Skutella, Williamson (2011) (factor 28).

We study the version where preemption is allowed. The difference is that 
elements can be fractionally scheduled (assigned to indices) and a set S is 
covered at the first time step when k(S) amount of elements in S are scheduled. 
We give a 2-approximation for this preemptive problem based on a novel linear 
programming relaxation. This guarantee is tight under Unique Games Conjecture. 
We also show that a preemptive schedule could be converted into a 
non-preemptive one with factor 6.2 loss in the performance. Combining two 
results we obtain 12.4-approximation for the non-preemptive Generalized Min Sum 
Set Cover Problem.

Minimum Latency Submodular Cover:
Minimum Latency Submodular Cover is a generalization of the Generalized Min Sum 
Set Cover, but also of Group Steiner Tree, Latency Group Steiner Tree and 
Submodular Ranking. We give a polylogarithmic approximation algorithm, enabled 
by simpler analysis of the logarithmic approximation for Submodular Ranking by 
Azar and  Gamzu (2011).