论文标题
节点加权施纳式问题问题的近似算法：具有添加奖品和图形奖品的图形的图形
Approximation algorithms for Node-weighted Steiner Problems: Digraphs with Additive Prizes and Graphs with Submodular Prizes
论文作者
论文摘要
在\ emph {预算的根节点加权的施泰纳树}问题中，我们获得了一个带有$ n $节点的图形$ g $，一个预定义的节点$ r $，与每个节点建模成本和奖品相关的两个权重。目的是在$ r $的$ g $中找到一棵树，以便其节点的总成本最多是给定的预算$ b $，并且总奖金最大化。在\ emph {配额根源加权的施泰纳树}问题中，我们给出了一个实价的配额$ q $，而不是预算，我们的目的是最大程度地减少植根于$ r $的树的成本，其总奖品至少为$ q $。 对于具有添加奖励功能的有向图的情况，我们开发了一种基于标准的基于流量的线性编程放松的技术，以计算一棵在奖品和成本之间进行良好权衡的树，这使我们能够为预算和配额问题提供非常简单的多项式时间近似算法。对于\ emph {预算}问题，我们的算法达到了双晶法属$（1+ε，o（\ frac {1} {ε^2} n^{2/3} \ ln {n} \ ln {n}）$ - 对于任何$ε\ in（0，1] $。接下来，使用基于流的LP，我们提供了一个令人惊讶的简单多项式$ O（（（1+ε）\ sqrt {n} {n} \ ln {n}）$ - 近似Algorth n diode node diend n n diend n diend n diode n diend n diode n diend n diode n diend n node n diend n node n n diend n n diend n n diend n n diend n n diend n n diend n n diode n diend n n diend n n diend n n diende n diode n dine版本问题，对于任何$ε> 0 $。 对于在节点子集上具有单调下奖品奖项的无向图的情况，我们提供多项式时间$ o（\ frac {1} {ε^3} \ sqrt {n} \ sqrt {n} \ log {n} \ log {n}）$ - 近似于预算的$ 1+三号$三的$三的$三号$三的; （0，1] $。我们的技术使我们能够为配额问题提供良好的近似值。
In the \emph{budgeted rooted node-weighted Steiner tree} problem, we are given a graph $G$ with $n$ nodes, a predefined node $r$, two weights associated to each node modelling costs and prizes. The aim is to find a tree in $G$ rooted at $r$ such that the total cost of its nodes is at most a given budget $B$ and the total prize is maximized. In the \emph{quota rooted node-weighted Steiner tree} problem, we are given a real-valued quota $Q$, instead of the budget, and we aim at minimizing the cost of a tree rooted at $r$ whose overall prize is at least $Q$. For the case of directed graphs with additive prize function, we develop a technique resorting on a standard flow-based linear programming relaxation to compute a tree with good trade-off between prize and cost, which allows us to provide very simple polynomial time approximation algorithms for both the budgeted and the quota problems. For the \emph{budgeted} problem, our algorithm achieves a bicriteria $(1+ε, O(\frac{1}{ε^2}n^{2/3}\ln{n}))$-approximation, for any $ε\in (0, 1]$. For the \emph{quota} problem, our algorithm guarantees a bicriteria approximation factor of $(2, O(n^{2/3}\ln{n}))$. Next, by using the flow-based LP, we provide a surprisingly simple polynomial time $O((1+ε)\sqrt{n} \ln {n})$-approximation algorithm for the node-weighted version of the directed Steiner tree problem, for any $ε>0$. For the case of undirected graphs with monotone submodular prize functions over subsets of nodes, we provide a polynomial time $O(\frac{1}{ε^3}\sqrt{n}\log{n})$-approximation algorithm for the budgeted problem that violates the budget constraint by a factor of at most $1+ε$, for any $ε\in (0, 1]$. Our technique allows us to provide a good approximation also for the quota problem.
