On the integrality ratio of semidefinite relaxations of MAX CUT

DOI10.1145/380752.380837zbMath1323.68298OpenAlexW1971195978MaRDI QIDQ5175999

Gideon Schechtman, Uriel Feige

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.380837

Mathematics Subject Classification ID

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) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (2)

A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems ⋮ Spectral bounds for unconstrained \((- 1,1)\)-quadratic optimization problems

Cites Work

• A constant-factor approximation algorithm for the k -median problem (extended abstract)

This page was built for publication: On the integrality ratio of semidefinite relaxations of MAX CUT