Sums-of-squares integer programming relaxation: Lecture 2

by Massimo Lauria

Lecture 2: Semidefinite programming and relaxations.

Scribe: Massimo Lauria


Semidefinite programs are a valuable tools in approximation algorithms and in combinatorial optimization, since semidefinite relaxations are usually stronger than linear ones. In this lecture we describe what is a semidefinite program.

Link: [Lecture notes 02]