Minimum-weight combinatorial structures under random cost-constraints

DOI10.37236/9152zbMATH Open1456.05145arXiv1910.08977OpenAlexW3129231088MaRDI QIDQ2223474FDOQ2223474

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)

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.

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

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

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

zbMATH Keywords

percolationrandom weighed graphs

Mathematics Subject Classification ID

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

Cites Work

• A note on two problems in connexion with graphs
• Probability Inequalities for Sums of Bounded Random Variables
• First passage percolation on random graphs with finite mean degrees
• One, Two and Three Times log n/n for Paths in a Complete Graph with Random Weights
• Weak disorder in the stochastic mean-field model of distance. II
• On Shortest Paths in Graphs with Random Weights
• On the value of a random minimum spanning tree problem
• On the Expected Value of a Random Assignment Problem
• A new rounding procedure for the assignment problem with applications to dense graph arrangement problems
• Maximum matchings in a class of random graphs
• Title not available (Why is that?)
• A note on log-concave random graphs
• Hamilton cycles in 3-out

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)