Probabilistic analysis of algorithms for cost constrained minimum weighted combinatorial objects
Probabilistic analysis of algorithms for cost constrained minimum weighted combinatorial objects
复制标题
DOI：
10.1016/j.orl.2021.04.003
复制
发表时间：
2021-04-28
影响因子：
1.1
通讯作者：
Tkocz, Tomasz
中科院分区：
文献类型：
--
作者：
Frieze, Alan;Tkocz, Tomasz
我们考虑了代价约束的最小生成树问题和分配问题。我们假设边权是连续随机变量Z的独立副本，它满足F(x) = P(z0)，其中alpha >= 1。此外，存在r = O(1)个预算约束，且边缘成本选择自相同分布。我们使用拉格朗日对偶构造多项式时间算法产生渐近最优解。对于生成树问题，我们允许r = 1，但对于分配问题，我们只能分析r = 1的情况。(C) 2021 Elsevier B.V.版权所有
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) = P(Z 0, where alpha >= 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. (C) 2021 Elsevier B.V. All rights reserved.