Approximation Algorithms and LP Relaxations for Scheduling Problems Related to Min-Sum Set Cover: a 2Δ-Approximation for 0/1 Processing Times and a (2Δ+ε)-Approximation in GeneralResearch Paper
Min-sum set cover asks for an order of the elements of a ground set that minimizes the average time at which a hyperedge is first covered. Feige, Lovász and Tetali showed that the greedy algorithm is a 4-approximation and that no better constant is possible unless P = NP (Feige, Lovász, Tetali 2004). Min-sum vertex cover, pipelined set cover,…