Constructing worst case instances for semidefinite programming based approximation algorithms

MaRDI QIDQ2768278zbMATH OpenFDO

Authors Noga Alon, Uri Zwick, Benny Sudakov

Publication date 30 January 2002

zbMATH Keywords

MAX CUT problemsemidefinite programming

Mathematics Subject Classification ID

Semidefinite programming (90C22) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Constructing worst case instances for semidefinite programming based approximation algorithms
• Semidefinite programming and approximation algorithms: a survey
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• scientific article; zbMATH DE number 1256761
• How Good is the Goemans--Williamson MAX CUT Algorithm?

Cited in

(1)

• Constructing worst case instances for semidefinite programming based approximation algorithms

This page was built for publication: Constructing worst case instances for semidefinite programming based approximation algorithms

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