Rounding the Lovász Theta Function with a Value Function Approximation

Rui Gong, Diego Cifuentes, Alejandro Toriello

The Lovász theta function is a semidefinite programming (SDP) relaxation for the maximum weighted stable set problem, which is tight for perfect graphs. However, even for perfect g…