We study the minimum spanning arborescence problem on the complete digraph [Formula: see text], 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 [Formula: see text] and U is uniform [Formula: see text]. There is also a constraint that the spanning arborescence T must satisfy [Formula: see text]. We establish, for a range of values for [Formula: see text], the asymptotic value of the optimum weight via the consideration of a dual problem.
No takes yet. Share an insight, caveat, or question.
Frieze et al. (2021) studied this question.
Synapse has enriched 5 related papers. Consider them for comparative context: