TY - GEN

T1 - Minimum latency submodular cover

AU - Zwaan, van der, G.R.J.

AU - Im, S.

AU - Nagarajan, V.

PY - 2012

Y1 - 2012

N2 - We study the submodular ranking problem in the presence of metric costs. The input to the minimum latency submodular cover (MLSC ) problem consists of a metric (V,d) with source r¿¿¿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; the cover time of function f i is the smallest value t such that f i has value one for the vertices visited within distance t along the path. This generalizes many previously studied problems, such as submodular ranking [1] when the metric is uniform, and group Steiner tree [14] when m¿=¿1 and f 1 is a coverage function. We give a polynomial time O(log1¿·log2+d|V|) -approximation algorithm for MLSC, where e¿>¿0 is the smallest non-zero marginal increase of any {fi}mi=1 and d¿>¿0 is any constant. This result is enabled by a simpler analysis of the submodular ranking algorithm from [1].
We also consider the stochastic submodular ranking problem where elements V have random instantiations, and obtain an adaptive algorithm with an O(log1/ e) approximation ratio, which is best possible. This result also generalizes several previously studied stochastic problems, eg. adaptive set cover [15] and shared filter evaluation [24,23].

AB - We study the submodular ranking problem in the presence of metric costs. The input to the minimum latency submodular cover (MLSC ) problem consists of a metric (V,d) with source r¿¿¿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; the cover time of function f i is the smallest value t such that f i has value one for the vertices visited within distance t along the path. This generalizes many previously studied problems, such as submodular ranking [1] when the metric is uniform, and group Steiner tree [14] when m¿=¿1 and f 1 is a coverage function. We give a polynomial time O(log1¿·log2+d|V|) -approximation algorithm for MLSC, where e¿>¿0 is the smallest non-zero marginal increase of any {fi}mi=1 and d¿>¿0 is any constant. This result is enabled by a simpler analysis of the submodular ranking algorithm from [1].
We also consider the stochastic submodular ranking problem where elements V have random instantiations, and obtain an adaptive algorithm with an O(log1/ e) approximation ratio, which is best possible. This result also generalizes several previously studied stochastic problems, eg. adaptive set cover [15] and shared filter evaluation [24,23].

U2 - 10.1007/978-3-642-31594-7_41

DO - 10.1007/978-3-642-31594-7_41

M3 - Conference contribution

SN - 978-3-642-31593-0

T3 - Lecture Notes in Computer Science

SP - 485

EP - 497

BT - Automata, Languages, and Programming (39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part I)

A2 - Czumaj, A.

A2 - Mehlhorn, K.

A2 - Pitts, A.

A2 - Wattenhofer, R.

PB - Springer

CY - Berlin

ER -