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

DOI10.37236/10237zbMath1506.05083arXiv2211.12348OpenAlexW4315853680MaRDI QIDQ2111788

Tomasz Tkocz, Yixue Liu, Albert Xu, Yun Cheng

Publication date: 17 January 2023

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

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

zbMATH Keywords

treeoptimizationassignment problemsGaussianrandom graphs

Mathematics Subject Classification ID

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

Related Items (1)

Extrema of a multinomial assignment process

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The lower tail of the random minimum spanning tree
• Threshold for the volume spanned by random points with independent coordinates
• An easy proof of the \(\zeta (2)\) limit in the random assignment problem
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• On the value of a random minimum spanning tree problem
• An algorithm for finding Hamilton paths and cycles in random graphs
• Probabilistic analysis of the generalised assignment problem
• The expected length of a shortest path
• A proof of Parisi's conjecture on the random assignment problem
• A note on random minimum length spanning trees
• On random multi-dimensional assignment problems
• Shortest paths with a cost constraint: a probabilistic analysis
• Probabilistic analysis of algorithms for cost constrained minimum weighted combinatorial objects
• Minimum-weight combinatorial structures under random cost-constraints
• A randomly weighted minimum spanning tree with a random cost constraint
• Maxima and near-maxima of a Gaussian random assignment field
• A general method for lower bounds on fluctuations of random variables
• Weak disorder asymptotics in the stochastic mean-field model of distance
• On the maximum of random assignment process
• The ?(2) limit in the random assignment problem
• Superconcentration and Related Topics
• Introduction to Random Graphs
• On the random 2-stage minimum spanning tree
• On the Difference of Expected Lengths of Minimum Spanning Trees
• A Patching Algorithm for the Nonsymmetric Traveling-Salesman Problem
• Constructive bounds and exact expectations for the random assignment problem
• The Distribution of Minimum-Weight Cliques and Other Subgraphs in Graphs with Random Edge Weights
• One, Two and Three Times log n/n for Paths in a Complete Graph with Random Weights
• The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph
• A Randomly Weighted Minimum Arborescence with a Random Cost Constraint
• On the Length of a Random Minimum Spanning Tree
• The Probabilistic Relationship Between the Assignment and Asymmetric Traveling Salesman Problems
• Proofs of the Parisi and Coppersmith‐Sorkin random assignment conjectures
• Minimum weight disk triangulations and fillings
• On multiple peaks and moderate deviations for the supremum of a Gaussian field

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