A randomly weighted minimum spanning tree with a random cost constraint

DOI10.37236/9445MaRDI QIDQ2223477zbMATH OpenOpenAlexFDO

Authors Tomasz Tkocz, Alan Frieze

Publication date 29 January 2021

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

asymptotic value of the optimum weightsymmetric logarithmic Sobolev inequality

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05)

Abstract: We study the minimum spanning tree problem on the complete graph $K_n$ where an edge $e$ has a weight $W_e$ and a cost $C_e$, each of which is an independent copy of the random variable $U^{g}amma$ where $gammaleq1$ and $U$ is the uniform $[0,1]$ random variable. There is also a constraint that the spanning tree $T$ must satisfy $C(T)leq{c}_0$. We establish, for a range of values for $c_0,gamma$, the asymptotic value of the optimum weight via the consideration of a dual problem.

Review text

Summary: We study the minimum spanning tree problem on the complete graph \(K_n\) where an edge \(e\) has a weight \(W_e\) and a cost \(C_e\), each of which is an independent copy of the random variable \(U^\gamma\) where \(\gamma\leq 1\) and \(U\) is the uniform \([0,1]\) random variable. There is also a constraint that the spanning tree \(T\) must satisfy \(C(T)\leq c_0\). We establish, for a range of values for \(c_0,\gamma \), the asymptotic value of the optimum weight via the consideration of a dual problem.

Recommendations

• A randomly weighted minimum arborescence with a random cost constraint
• Minimum-weight combinatorial structures under random cost-constraints
• On the value of a random minimum spanning tree problem
• The minimum weight spanning tree with constraints
• On random minimum length spanning trees

Cites work

• A note on log-concave random graphs
• A note on random minimum length spanning trees
• An application of lagrangean decomposition to the resource-constrained minimum weighted arborescence problem
• Concentration inequalities using the entropy method
• scientific article; zbMATH DE number 1123759 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• On random minimum length spanning trees
• On the difference of expected lengths of minimum spanning trees
• On the length of a random minimum spanning tree
• On the value of a random minimum spanning tree problem
• One, Two and Three Times log n/n for Paths in a Complete Graph with Random Weights
• Random minimum length spanning trees in regular graphs
• The constrained minimum spanning tree problem
• The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph

Cited in

(10)

• 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
• Random-tree diameter and the diameter-constrained MST
• On finding a minimum spanning tree in a network with random weights
• OPTIMAL PATH AND MINIMAL SPANNING TREES IN RANDOM WEIGHTED NETWORKS
• Random-tree Diameter and the Diameter-constrained MST
• A randomly weighted minimum arborescence with a random cost constraint
• Randomization Helps Computing a Minimum Spanning Tree under Uncertainty
• The lower tail of the random minimum spanning tree

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

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