Max cut and semidefinite rank

DOI10.1016/J.ORL.2024.107067MaRDI QIDQ6564284

David P. Williamson, Renee Mirka

Publication date: 1 July 2024

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

zbMATH Keywords

semidefinite programminggraphsmatrix rankmax cut

Mathematics Subject Classification ID

Operations research, mathematical programming (90-XX)

Cites Work

• Graph coloring and semidefinite rank
• Rank-two relaxation heuristics for MAX-CUT and other binary quadratic programs
• P-Complete Approximation Problems
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• On the cut polytope
• Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
• Max Cut and the Smallest Eigenvalue
• Reducibility among Combinatorial Problems

This page was built for publication: Max cut and semidefinite rank

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