A randomly weighted minimum arborescence with a random cost constraint

DOI10.1287/MOOR.2021.1184MaRDI QIDQ5085156zbMATH OpenOpenAlexFDO

Authors Tomasz Tkocz, Alan Frieze

Publication date 27 June 2022

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1907.03375

zbMATH Keywords

cost constraintrandom minimum spanning arborescence

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial optimization (90C27)

Abstract: We study the minimum spanning arborescence problem on the complete digraph $vec{K}_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^{a}lpha$ where $alphaleq1$ and $U$ is uniform $[0,1]$. There is also a constraint that the spanning arborescence $T$ must satisfy $C(T)leq{c}_0$. We establish, for a range of values for $c_0,alpha$, the asymptotic value of the optimum weight via the consideration of a dual problem.

Recommendations

• A randomly weighted minimum spanning tree with a random cost constraint
• Minimum-weight combinatorial structures under random cost-constraints
• The weighted arborescence constraint
• Robustness of minimum cost arborescences
• scientific article; zbMATH DE number 7692724

Cites work

• A randomly weighted minimum spanning tree with a random cost constraint
• A randomly weighted minimum spanning tree with a random cost constraint
• An application of lagrangean decomposition to the resource-constrained minimum weighted arborescence problem
• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• scientific article; zbMATH DE number 3932819 (Why is no real title available?)
• scientific article; zbMATH DE number 193411 (Why is no real title available?)
• One, Two and Three Times log n/n for Paths in a Complete Graph with Random Weights
• Optimum branchings
• Probability Inequalities for Sums of Bounded Random Variables
• The constrained minimum spanning tree problem

Cited in

(9)

• Probabilistic analysis of algorithms for cost constrained minimum weighted combinatorial objects
• Typical values of extremal-weight combinatorial structures with independent symmetric weights
• Minimum-weight combinatorial structures under random cost-constraints
• A randomly weighted minimum spanning tree with a random cost constraint
• An application of lagrangean decomposition to the resource-constrained minimum weighted arborescence problem
• Limit Laws for the Optimal Directed Tree with Random Costs
• Precedence-constrained arborescences
• A branch-and-bound algorithm for the precedence-constrained minimum-cost arborescence problem
• Target-based distributionally robust minimum spanning tree problem

This page was built for publication: A randomly weighted minimum arborescence with a random cost constraint

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5085156)