Approximating Min-sum Set Cover

摘要

The input to the min sum set cover problem is a collection of n sets that jointly cover m elements. The output is a linear order on the sets, namely, in every time step from 1 to n exactly one set is chosen. For every element, this induces a first time step by which it is covered. The objective is to find a linear arrangement of the sets that minimizes the sum of these first time steps over all elements. We show that a greedy algorithm approximates min sum set cover within a ratio of 4. This result was implicit in work of Bar-Noy, Bellare, Hall-dorsson, Shachnai and Tamir (1998) on chromatic sums, but we present a simpler proof. We also show that for every ε > 0, achieving an approximation ratio of 4 - ε is NP-hard. For the min sum vertex cover version of the problem, we show that it can be approximated within a ratio of 2, and is NP-hard to approximate within some constant ρ > 1.