Sums-of-squares integer programming relaxation: Lecture 1

by Massimo Lauria

Lecture 1: Linear relaxations of integer programs.

Scribe: Massimo Lauria


We can express combinatorial problems using integer programs and, since we can’t solve them, we consider relaxed programs in which integer constraints are relaxed to linear ones. Then we round fractional solutions to integer. We consider hierarchies of linear programs and discuss the quality of the corresponding solutions.}

Link: [Lecture notes 01]