Typical values of extremal-weight combinatorial structures with independent symmetric weights

DOI10.37236/10237MaRDI QIDQ2111788zbMATH OpenOpenAlexFDO

Authors Yun Cheng, Yixue Liu, Tomasz Tkocz, Albert Xu

Publication date 17 January 2023

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/2211.12348

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

treeoptimizationassignment problemsrandom graphsGaussian

Mathematics Subject Classification ID

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

Abstract: Suppose that the edges of a complete graph are assigned weights independently at random and we ask for the weight of the minimal-weight spanning tree, or perfect matching, or Hamiltonian cycle. For these and several other common optimisation problems, we establish asymptotically tight bounds when the weights are independent copies of a symmetric random variable (satisfying a mild condition on tail probabilities), in particular when the weights are Gaussian.

Recommendations

• On the symmetry and asymmetry of combinatorial structures
• scientific article; zbMATH DE number 1285774
• Enumeration of the edge weights of symmetrically designed graphs
• Weight-dependent commutation relations and combinatorial identities
• scientific article; zbMATH DE number 1075005
• Extremal Estrada indices of the weighted trees with fixed total weight sum
• The exact weighted independent set problem in perfect graphs and related classes
• The combinatorics of weighted vector compositions
• On the total weight of arrangements of halfplanes
• scientific article; zbMATH DE number 1150117

Cites work

• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 4170917 (Why is no real title available?)
• scientific article; zbMATH DE number 3216216 (Why is no real title available?)
• A Patching Algorithm for the Nonsymmetric Traveling-Salesman Problem
• A general method for lower bounds on fluctuations of random variables
• A note on random minimum length spanning trees
• A proof of Parisi's conjecture on the random assignment problem
• A randomly weighted minimum arborescence with a random cost constraint
• A randomly weighted minimum spanning tree with a random cost constraint
• An algorithm for finding Hamilton paths and cycles in random graphs
• An easy proof of the \(\zeta (2)\) limit in the random assignment problem
• Constructive bounds and exact expectations for the random assignment problem
• Introduction to Random Graphs
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• Maxima and near-maxima of a Gaussian random assignment field
• Minimum weight disk triangulations and fillings
• Minimum-weight combinatorial structures under random cost-constraints
• On multiple peaks and moderate deviations for the supremum of a Gaussian field
• On random multi-dimensional assignment problems
• On the difference of expected lengths of minimum spanning trees
• On the length of a random minimum spanning tree
• On the maximum of random assignment process
• On the random 2-stage 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
• Probabilistic analysis of algorithms for cost constrained minimum weighted combinatorial objects
• Probabilistic analysis of the generalised assignment problem
• Proofs of the Parisi and Coppersmith‐Sorkin random assignment conjectures
• Shortest paths with a cost constraint: a probabilistic analysis
• Superconcentration and related topics
• The Probabilistic Relationship Between the Assignment and Asymmetric Traveling Salesman Problems
• The \(\zeta(2)\) limit in the random assignment problem
• The concentration of measure phenomenon
• The distribution of minimum-weight cliques and other subgraphs in graphs with random edge weights
• The expected length of a shortest path
• The lower tail of the random minimum spanning tree
• The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph
• Threshold for the volume spanned by random points with independent coordinates
• Weak disorder asymptotics in the stochastic mean-field model of distance

Cited in

(3)

• Maximization problems on graphs with edge weights chosen from a normal distribution (extended abstract)
• Extrema of a multinomial assignment process
• The effect of adding randomly weighted edges

This page was built for publication: Typical values of extremal-weight combinatorial structures with independent symmetric weights

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