论文标题
成本约束最小加权组合对象的算法的概率分析
Probabilistic analysis of algorithms for cost constrained minimum weighted combinatorial objects
论文作者
论文摘要
我们考虑最小跨越树问题和分配问题的成本约束版本。我们假设边缘权重是满足$ f（x）= \ pr（z \ leq x）\ of x^α$ as $ x \ to0 $的连续随机变量$ z $的独立副本。此外，还有$ r = o（1）$预算约束，从同一分布中选择的边缘成本。我们使用拉格朗日二元性来构建产生渐近最佳解的多项式时间算法。对于生成树问题，我们允许$ r> 1 $，但是对于分配问题，我们只能分析案例$ r = 1 $。
We consider cost constrained versions of the minimum spanning tree problem and the assignment problem. We assume edge weights are independent copies of a continuous random variable $Z$ that satisfies $F(x)=\Pr(Z\leq x)\approx x^α$ as $x\to0$, where $α\geq 1$. Also, there are $r=O(1)$ budget constraints with edge costs chosen from the same distribution. We use Lagrangean duality to construct polynomial time algorithms that produce asymptotically optimal solutions. For the spanning tree problem, we allow $r>1$, but for the assignment problem we can only analyse the case $r=1$.
