Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming
From MaRDI portal
Publication:5176000
DOI10.1145/380752.380838zbMath1323.90047OpenAlexW2063046368MaRDI QIDQ5176000
David P. Williamson, Michel X. Goemans
Publication date: 27 February 2015
Published in: Proceedings of the thirty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/380752.380838
Analysis of algorithms and problem complexity (68Q25) Semidefinite programming (90C22) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items
Is constraint satisfaction over two variables always easy? ⋮ Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming ⋮ Angular synchronization by eigenvectors and semidefinite programming ⋮ An approximation algorithm for scheduling two parallel machines with capacity constraints.
Cites Work
