Minimum latency submodular cover

G.R.J. Zwaan, van der, S. Im, V. Nagarajan

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

6 Citations (Scopus)

Abstract

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].
Original languageEnglish
Title of host publicationAutomata, Languages, and Programming (39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part I)
EditorsA. Czumaj, K. Mehlhorn, A. Pitts, R. Wattenhofer
Place of PublicationBerlin
PublisherSpringer
Pages485-497
ISBN (Print)978-3-642-31593-0
DOIs
Publication statusPublished - 2012
Externally publishedYes

Publication series

NameLecture Notes in Computer Science
Volume7391
ISSN (Print)0302-9743

Fingerprint

Dive into the research topics of 'Minimum latency submodular cover'. Together they form a unique fingerprint.

Cite this