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