An Approximation Algorithm for the Connected Maximum Coverage Problem in Directed Graphs

Abstract

In the Directed rooted Connected Budgeted maximum Coverage problem (\DRCC), we are given a collection of subsets $\mathcal{S}$, defined over a ground set $X$, and a directed graph $G=(V,E)$, where each node is associated with a set of $\mathcal{S}$. Each set in $\mathcal{S}$ has a different cost and each element of $X$ gives a different prize. The goal is to find a subcollection ${\mathcal{S}}^{\prime }\subseteq \mathcal{S}$ such that ${\mathcal{S}}^{\prime }$ induces an out-tree rooted at a given node, the total cost of the sets in ${\mathcal{S}}^{\prime }$ does not exceed a budget $B$, and the total prize of the elements covered by ${\mathcal{S}}^{\prime }$ is maximized. In this paper, we provide an algorithm for \DRCC that guarantees an approximation ratio of $O\left(\frac{\sqrt{|V|}{\log }^2|X|}{{\epsilon }^2}\right)$, with a budget violation of a factor $1+\epsilon$, where $\epsilon \in (0,1]$. Our algorithm also implies an improved approximation factor for the budgeted node-weighted Steiner problem in directed graphs, a particular case of \DRCC where the prize function is additive, for which we improve from $O\left(\frac{1}{{\epsilon }^2}|V{|}^{2/3}\log |V|\right)$ to $O\left(\frac{1}{{\epsilon }^2}|V{|}^{1/2}{\log }^2|V|\right)$.