Minimum Latency Submodular Cover

Details Minimum Latency Submodular Cover Minimum Latency Submodular Cover

2011-10-10

arxiv.org/abs/1110.2207v2

Computer Science

Data Structures and Algorithms

27 pages, 1 figure

Scientific paper

We study the submodular ranking problem in the presence of metric costs. This is motivated by applications in broadcast scheduling and web-search ranking. The input to the minimum latency submodular cover (MLSC) problem consists of a metric $(V,d)$ with source $r\in V$ and $m$ monotone submodular functions $f_1, f_2, ..., f_m: 2^V \rightarrow [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 on the vertices visited within distance $t$ along the path. We give a polynomial time $O(\log \frac1\eps \cdot \log^{2+\delta} |V|)$-approximation algorithm for this problem; here $\delta>0$ is any constant, and $\eps$ is the minimum positive marginal increase of any function $f_i$. When the underlying metric is uniform, we obtain the Submodular Ranking (SR), for which an $O(\log \frac1\eps)$-approximation algorithm was given by Azar and Gamzu [AzarG11]. In fact, our general result is enabled by a simpler analysis of [AzarG11]. We also consider the latency covering Steiner tree problem (LCST), which is an interesting special case of MLSC. Here, each function $f_i$ is associated with a group $g_i\subseteq V$ and requirement $k_i$ such that $f_i(S) = \min{\frac{|g_i\cap S|}{k_i},\, 1}$. This is a natural generalization of the latency covering Steiner tree and generalized min-sum set cover problems. We obtain an $O(\log^2|V|)$-approximation algorithm for LCST. This relies on a new and stronger LP relaxation for covering Steiner tree, that might be of independent interest. Finally, in a somewhat different direction, we consider the stochastic SR, and obtain an $O(\log 1/ \eps)$-approximation algorithm, which is best possible. Our result generalizes several previously studied stochastic problems.

Affiliated with

Also associated with

No associations

Rating

Minimum Latency Submodular Cover does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Minimum Latency Submodular Cover, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Minimum Latency Submodular Cover will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-471068