Geodesic
Typical values of extremal-weight combinatorial structures with independent symmetric weights
Yun Cheng ; Yixue Liu ; Tomasz Tkocz1 ; Albert Xu
1Carnegie Mellon University
The electronic journal of combinatorics, Tome 30 (2023) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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.
DOI : 10.37236/10237
Classification : 05C22, 05C80, 90C27, 60C05
Mots-clés : tree, optimization, Gaussian, assignment problems, random graphs

Yun Cheng    ; Yixue Liu    ; Tomasz Tkocz  1   ; Albert Xu 

1 Carnegie Mellon University 
@article{10_37236_10237,
     author = {Yun Cheng and Yixue Liu and Tomasz Tkocz and Albert Xu},
     title = {Typical values of extremal-weight combinatorial structures with independent symmetric weights},
     journal = {The electronic journal of combinatorics},
     year = {2023},
     volume = {30},
     number = {1},
     doi = {10.37236/10237},
     zbl = {1506.05083},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/10237/}
}
TY  - JOUR
AU  - Yun Cheng
AU  - Yixue Liu
AU  - Tomasz Tkocz
AU  - Albert Xu
TI  - Typical values of extremal-weight combinatorial structures with independent symmetric weights
JO  - The electronic journal of combinatorics
PY  - 2023
VL  - 30
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/10237/
DO  - 10.37236/10237
ID  - 10_37236_10237
ER  - 
%0 Journal Article
%A Yun Cheng
%A Yixue Liu
%A Tomasz Tkocz
%A Albert Xu
%T Typical values of extremal-weight combinatorial structures with independent symmetric weights
%J The electronic journal of combinatorics
%D 2023
%V 30
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/10237/
%R 10.37236/10237
%F 10_37236_10237
Yun Cheng; Yixue Liu; Tomasz Tkocz; Albert Xu. Typical values of extremal-weight combinatorial structures with independent symmetric weights. The electronic journal of combinatorics, Tome 30 (2023) no. 1. doi: 10.37236/10237

Cité par Sources :