Instance-specific linear relaxations of semidefinite optimization problems

Daniel de Roux, Robert Carr, R. Ravi

We introduce a generic technique to obtain linear relaxations of semidefinite programs with provable guarantees based on the commutativity of the constraint and the objective matri…