Preemptive and Non-Preemptive Generalized Min Sum Set Cover

Sungjin Im, Maxim Sviridenko & Ruben Van Der Zwaan
In the (non-preemptive) Generalized Min Sum Set Cover Problem, we are given n ground elements and a collection of sets S = {S_1, S_2, ..., S_m} where each set S_i in 2^{[n]} has a positive requirement k(S_i) that has to be fulfilled. We would like to order all elements to minimize the total (weighted) cover time of all sets. The cover time of a set S_i is defined as the first index j in the...