Preemptive and non-preemptive generalized min sum set cover

• 成果类型: Article
• 署名作者: Im, Sungjin; Sviridenko, Maxim; van der Zwaan, Ruben
• 署名单位: Duke University; University of Warwick; Maastricht University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-013-0651-2
• 发表日期: 2014
• 页码: 377-401
• 关键词: single-machine; algorithm

摘要

In the (non-preemptive) Generalized Min Sum Set Cover Problem, we are given ground elements and a collection of sets where each set has a positive requirement 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 is defined as the first index in the ordering such that the first elements in the ordering contain elements in . This problem was introduced by Azar et al. (2009) with interesting motivations in web page ranking and broadcast scheduling. For this problem, constant approximations are known by Bansal et al. (2010) and Skutella and Williamson (Oper Res Lett 39(6):433-436, 2011). We study the version where preemption is allowed. The difference is that elements can be fractionally scheduled and a set is covered in the moment when amount of elements in are scheduled. We give a 2-approximation for this preemptive problem. Our linear programming relaxation and analysis are completely different from the aforementioned previous works. We also show that any preemptive solution can be transformed into a non-preemptive one by losing a factor of 6.2 in the objective function. As a byproduct, we obtain an improved -approximation for the non-preemptive problem.