Lower Bounds for Max-Cut via Semidefinite Programming.
Charles CarlsonAlexandra KollaRay LiNitya ManiBenny SudakovLuca TrevisanPublished in: LATIN (2020)
Keyphrases
- semidefinite programming
- max cut
- lower bound
- np hard
- linear programming
- upper bound
- graph model
- optimal solution
- graph partitioning
- objective function
- primal dual
- linear program
- worst case
- branch and bound
- kernel matrix
- planar graphs
- approximation algorithms
- np complete
- np complete problems
- maximum margin
- image segmentation
- graphical models