Improved approximations for min sum vertex cover and generalized min sum set cover

We study the generalized min sum set cover (GMSSC) problem, wherein given a collection of hyperedges E with arbitrary covering requirements {ke ∈ Z+ : e ∈ E}, the goal is to find an ordering of the vertices to minimize the total cover time of the hyperedges; a hyperedge e is considered covered by the first time when ke many of its vertices appear in the ordering. We give a 4.642 approximation algorithm for GMSSC, coming close to the best possible bound of 4, already for the classical special case (with all ke = 1) of min sum set cover (MSSC) studied by Feige, Lovász and Tetali [11], and improving upon the previous best known bound of 12.4 due to Im, Sviridenko and van der Zwaan [20]. Our algorithm is based on transforming the LP solution by a suitable kernel and applying randomized rounding. This also gives an LP-based 4 approximation for MSSC. As part of the analysis of our algorithm, we also derive an inequality on the lower tail of a sum of independent Bernoulli random variables, which might be of independent interest and broader utility. Another well-known special case is the min sum vertex cover (MSVC) problem, in which the input hypergraph is a graph (i.e., |e| = 2) and ke = 1, for every edge e ∈ E. We give a 16/9 ' 1.778 approximation for MSVC, and show a matching integrality gap for the natural LP relaxation. This improves upon the previous best 1.999946 approximation of Barenholz, Feige and Peleg [6]. (The claimed 1.79 approximation result of Iwata, Tetali and Tripathi [21] for the MSVC turned out have an unfortunate, seemingly unfixable, mistake in it.) Finally, we revisit MSSC and consider the lp norm of cover-time of the hyperedges. Using a dual fitting argument, we show that the natural greedy algorithm simultaneously achieves approximation guarantees of (p + 1)1+1/p, for all p ≥ 1, giving another proof of the result of Golovin, Gupta, Kumar and Tangwongsan [13], and showing its tightness up to NP-hardness. For p = 1, this gives yet another proof of the 4 approximation for MSSC.

• View at Publisher

Free Full Text ( Final Version , 467kb )