Minimum Latency Submodular Cover

作者：Im Sungjin^*; Nagarajan Viswanath; Van der Zwaan Ruben

来源：ACM Transactions on Algorithms, 2016, 13(1): 13.

DOI：10.1145/2987751

• Approximation
• sequencing and scheduling
• submodular
• stochastic optimization
• covering Steiner tree

We study the Minimum Latency Submodular Cover (MLSC) problem, which consists of a metric (V, d) with source r is an element of V and m monotone submodular functions f(1), f(2), ... , f(m) : 2(V) -> [ 0, 1]. The goal is to find a path originating at r that minimizes the total "cover time" of all functions. This generalizes well-studied problems, such as Submodular Ranking [ Azar and Gamzu 2011] and the Group Steiner Tree [ Garg et al. 2000]. We give a polynomial time O(log 1/epsilon . log(2+delta) vertical bar V vertical bar)-approximation algorithm for MLSC, where epsilon > 0 is the smallest non-zero marginal increase of any {f(i)}(i=1)(m) and delta > 0 is any constant. We also consider the Latency Covering Steiner Tree (LCST) problem, which is the special case of MLSC where the f(i)s are multi-coverage functions. This is a common generalization of the Latency Group Steiner Tree [Gupta et al. 2010; Chakrabarty and Swamy 2011] and Generalized Min-sum Set Cover [ Azar et al. 2009; Bansal et al. 2010] problems. We obtain an O(log(2) vertical bar V vertical bar)-approximation algorithm for LCST. Finally, we study a natural stochastic extension of the Submodular Ranking problem and obtain an adaptive algorithm with an O(log 1/epsilon)-approximation ratio, which is best possible. This result also generalizes some previously studied stochastic optimization problems, such as Stochastic Set Cover [Goemans and Vondrak 2006] and Shared Filter Evaluation [Munagala et al. 2007; Liu et al. 2008].

• 出版日期2016-12