Minimum-weight combinatorial structures under random cost-constraints

DOI10.37236/9152MaRDI QIDQ2223474zbMATH OpenOpenAlexFDO

Authors Wesley Pegden, Gregory B. Sorkin, 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/1910.08977

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

percolationrandom weighed graphs

Mathematics Subject Classification ID

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

Abstract: Recall that Janson showed that if the edges of the complete graph $K_n$ are assigned exponentially distributed independent random weights, then the expected length of a shortest path between a fixed pair of vertices is asymptotically equal to $(logn)/n$. We consider analogous problems where edges have not only a random length but also a random cost, and we are interested in the length of the minimum-length structure whose total cost is less than some cost budget. For several classes of structures, we determine the correct minimum length structure as a function of the cost-budget, up to constant factors. Moreover, we achieve this even in the more general setting where the distribution of weights and costs are arbitrary, so long as the density $f(x)$ as $xo0$ behaves like $c{x}^{g}amma$ for some $gammageq0$; previously, this case was not understood even in the absence of cost constraints. We also handle the case where each edge has several independent costs associated to it, and we must simultaneously satisfy budgets on each cost. In this case, we show that the minimum-length structure obtainable is essentially controlled by the product of the cost thresholds.

Recommendations

• Shortest paths with a cost constraint: a probabilistic analysis
• On the value of a random minimum spanning tree problem
• A randomly weighted minimum spanning tree with a random cost constraint
• A randomly weighted minimum arborescence with a random cost constraint
• Successive shortest paths in complete graphs with random edge weights

Cites work

• scientific article; zbMATH DE number 1496581 (Why is no real title available?)
• A new rounding procedure for the assignment problem with applications to dense graph arrangement problems
• A note on log-concave random graphs
• A note on two problems in connexion with graphs
• First passage percolation on random graphs with finite mean degrees
• Hamilton cycles in 3-out
• Maximum matchings in a class of random graphs
• On Shortest Paths in Graphs with Random Weights
• On the Expected Value of a Random Assignment Problem
• 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
• Probability Inequalities for Sums of Bounded Random Variables
• Weak disorder in the stochastic mean-field model of distance. II

Cited in

(8)

• Weighted Minimum-Length Rearrangement Scenarios.
• Typical values of extremal-weight combinatorial structures with independent symmetric weights
• Average-Case Analyses of Vickrey Costs
• Energy of convex sets, shortest paths, and resistance
• Shortest paths with a cost constraint: a probabilistic analysis
• A randomly weighted minimum arborescence with a random cost constraint
• Probabilistic analysis of algorithms for cost constrained minimum weighted combinatorial objects
• A randomly weighted minimum spanning tree with a random cost constraint

This page was built for publication: Minimum-weight combinatorial structures under random cost-constraints

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