A probabilistic result for the max-cut problem on random graphs

DOI10.1016/S0167-6377(00)00055-9zbMath0991.90138OpenAlexW2022436041WikidataQ127363191 ScholiaQ127363191MaRDI QIDQ5929142

Amir Beck, Marc Teboulle

Publication date: 2001

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0167-6377(00)00055-9

zbMATH Keywords

eigenvalues of random matricesmaximum cutprobabilistic analysis

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Stochastic network models in operations research (90B15)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The eigenvalues of random symmetric matrices
• Semidefinite programming in combinatorial optimization
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• A new 5‐arc‐transitive cubic graph

This page was built for publication: A probabilistic result for the max-cut problem on random graphs