论文标题
预算的外树最大化和次生奖
Budgeted Out-tree Maximization with Submodular Prizes
论文作者
论文摘要
我们考虑了收集施主树问题的变体，其中我们将获得\ emph {有向图} $ d =（v，a）$，单调下一个奖品奖励$ p：2^v \ rightarrow \ rightarrow \ mathbb {r}^+ \ cup \ cup \ cup \ {0 \} root vertex $ r \ in V $，预算$ b $。目的是找到一个基于$ r $的$ d $的$ t $ t $，最多$ b $，并最大化奖品功能。我们称此问题为\ emph {定向扎根的suppoular树}（\ textbf {drso}）。 最近，Ghuge和Nagarajan [Soda \ 2020]给出了一个最佳的准级polynomial $ o \ left（\ frac {\ frac {\ log n'} {\ log log \ log \ log \ log n'} \ right）$ - 近似算法，其中$ n'$是最佳解决方案的数量，而该范围是一个最佳的范围。 在本文中，我们为\ textbf {drso}提供多项式时间算法，保证$ o（\ sqrt {b}/ε^3）$的近似因素，以预算违反$ 1+ε$的预算违反（0,1，1，1，1,1，1,1，，1,1，，1,1，，1,1，，1,1，，1,1，，1,1，1,1，1,1，1,1，1,1，，1,1，1,1，，1,1，1,1，，1,1，，1,1，1,1，，1,1）$。多项式时间近似算法，我们进一步表明，\ textbf {drso}的无根据的版本可以近似于$ O（\ sqrt {b}）$，而无需违反预算trans。\ netw。\ 2015]对于无方向和无根据的情况，$δ$是图的最大程度，我们为几个相关问题提供了一些新的/改进的近似范围，包括\ textbf {drso的添加剂版本}，最大预算连接的封面问题，以及预算的传感器问题。
We consider a variant of the prize collecting Steiner tree problem in which we are given a \emph{directed graph} $D=(V,A)$, a monotone submodular prize function $p:2^V \rightarrow \mathbb{R}^+ \cup \{0\}$, a cost function $c:V \rightarrow \mathbb{Z}^{+}$, a root vertex $r \in V$, and a budget $B$. The aim is to find an out-subtree $T$ of $D$ rooted at $r$ that costs at most $B$ and maximizes the prize function. We call this problem \emph{Directed Rooted Submodular Tree} (\textbf{DRSO}). Very recently, Ghuge and Nagarajan [SODA\ 2020] gave an optimal quasi-polynomial-time $O\left(\frac{\log n'}{\log \log n'}\right)$-approximation algorithm, where $n'$ is the number of vertices in an optimal solution, for the case in which the costs are associated to the edges. In this paper, we give a polynomial-time algorithm for \textbf{DRSO} that guarantees an approximation factor of $O(\sqrt{B}/ε^3)$ at the cost of a budget violation of a factor $1+ε$, for any $ε\in (0,1]$. The same result holds for the edge-cost case, to the best of our knowledge this is the first polynomial-time approximation algorithm for this case. We further show that the unrooted version of \textbf{DRSO} can be approximated to a factor of $O(\sqrt{B})$ without budget violation, which is an improvement over the factor $O(Δ\sqrt{B})$ given in~[Kuo et al.\ IEEE/ACM\ Trans.\ Netw.\ 2015] for the undirected and unrooted case, where $Δ$ is the maximum degree of the graph. Finally, we provide some new/improved approximation bounds for several related problems, including the additive-prize version of \textbf{DRSO}, the maximum budgeted connected set cover problem, and the budgeted sensor cover problem.
