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

DOI10.1016/S0167-6377(00)00055-9MaRDI QIDQ5929142zbMATH OpenOpenAlexWikidataFDO

Authors 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

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

Recommendations

• On the max-cut of sparse random graphs
• On the maximal cut in a random hypergraph
• The expected relative error of the polyhedral approximation of the max- cut problem
• The MAX-CUT of sparse random graphs
• scientific article; zbMATH DE number 1107723

Cites work

• A new 5‐arc‐transitive cubic graph
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 510844 (Why is no real title available?)
• scientific article; zbMATH DE number 3249395 (Why is no real title available?)
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Semidefinite programming in combinatorial optimization
• The eigenvalues of random symmetric matrices

Cited in

(9)

• Balanced cut approximation in random geometric graphs
• A lower bound of the expected maximum number of edge-disjoint \(s\)--\(t\) paths on probabilistic graphs
• The expected relative error of the polyhedral approximation of the max- cut problem
• On the unbalanced cut problem and the generalized Sherrington-Kirkpatrick model
• On the maximal cut in a random hypergraph
• Extremal cuts of sparse random graphs
• scientific article; zbMATH DE number 1107723 (Why is no real title available?)
• On the max-cut of sparse random graphs
• The cut metric, random graphs, and branching processes

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5929142)