ON MIN SUM VERTEX COVER AND GENERALIZED MIN SUM SET COVER

作     者：Bansal, Nikhil Batra, Jatin Farhadi, Majid Tetali, Prasad 

作者机构：Univ Michigan Dept Comp Sci & Engn Ann Arbor MI 48109 USA Tata Inst Fundamental Res Sch Technol & Comp Sci Mumbai 400005 India Jump Trading LLC Chicago IL 60654 USA Carnegie Mellon Univ Dept Math Sci Pittsburgh PA 15213 USA 

出 版 物：《SIAM JOURNAL ON COMPUTING》 (SIAM J Comput)

年 卷 期：2023年第52卷第2期

页      面：327-357页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：NWO Vici grant [639.023.812] NSF [TRIPODS-1740776] ACO Ph.D. Program 

主　　题：randomized algorithms approximation algorithms hardness of approximation scheduling convex programming tails of probability distributions 

摘      要：We study the Generalized Min Sum Set Cover (GMSSC) problem, wherein given a collection of hyperedges E with arbitrary covering requirements {ke \in Z+ : e \in 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 and 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\ asz, and Tetali, and improving upon the previous best known bound of 12.4 due to Im, Sviridenko, and van der Zwaan. Our algorithm is based on transforming the LP solution by a suitable kernel and applying randomized rounding. 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. Min Sum Vertex Cover (MSVC) is a well-known special case of MSSC in which the input hypergraph is a graph (i.e., lel = 2) and ke = 1 for every edge e \in E. We give a 16/9 \simeq 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. Finally, we revisit MSSC and consider the \ellp norm of cover-time of the hyperedges. Using a dual fitting argument, we show that the natural greedy algorithm achieves tight, up to NP-hardness, approximation guarantees of (p + 1)1+1/p for all p\geq 1, giving another proof of the result of Golovin, Gupta, Kumar, and Tangwongsan, and showing its tightness up to NP-hardness. For p = 1, this gives yet another proof of the 4 approximation for MSSC.