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

DOI10.37236/10237zbMATH Open1506.05083arXiv2211.12348OpenAlexW4315853680MaRDI QIDQ2111788FDOQ2111788

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)

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.

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

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

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

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)

Cites Work

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

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)