A Randomly Weighted Minimum Arborescence with a Random Cost Constraint
成果类型：
Article
署名作者：
Frieze, Alan M.; Tkocz, Tomasz
署名单位：
Carnegie Mellon University
刊物名称：
MATHEMATICS OF OPERATIONS RESEARCH
ISSN/ISSBN：
0364-765X
DOI：
10.1287/moor.2021.1184
发表日期：
2022
页码：
1664-1680
关键词：
摘要：
We study the minimum spanning arborescence problem on the complete digraph (K) over right arrow (n), where an edge e has a weight W-e and a cost C-e, each of which is an independent uniform random variable U-s, where 0 < s <= 1 and U is uniform [0,1]. There is also a constraint that the spanning arborescence T must satisfy C(T) <= c(0). We establish, for a range of values for c(0),s, the asymptotic value of the optimum weight via the consideration of a dual problem.
来源URL：