Dimension reduction for maximum matchings and the fastest mixing Markov chain

DOI10.5802/crmath.447zbMath1520.05088arXiv2203.03858OpenAlexW4384692454MaRDI QIDQ6117114

Thuy Duong Vuong, Huy-Tuan Pham, Vishesh Jain

Publication date: 19 July 2023

Published in: Comptes Rendus. Mathématique. Académie des Sciences, Paris (Search for Journal in Brave)

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

zbMATH Keywords

weighted graphundirected graph(fractional) matching number

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Signed and weighted graphs (05C22)

Cites Work

• Unnamed Item
• Semidefinite programming in combinatorial optimization
• Bounding fastest mixing
• Graph expansion and the unique games conjecture
• Fastest Mixing Markov Chain on Graphs with Symmetries
• Fastest Mixing Markov Chain on a Graph
• Performance of Johnson-Lindenstrauss transform for k -means and k -medians clustering
• Geometry of cuts and metrics