Invited Session Tue.2.H 3005

Tuesday, 13:15 - 14:45 h, Room: H 3005

Cluster 2: Combinatorial optimization [...]

Lift-and-project methods for combinatorial optimization problems

Tuesday, 13:15 - 13:40 h, Room: H 3005, Talk 1

Eden Chlamtac
Reduced integrality gaps and improved approximations via lift-and-project methods

Abstract:
We consider natural convex relaxations of integer programs, such as linear programs (LP) and semi-definite programs (SDP), and examine how well they approximate various problems in combinatorial optimization. The "integrality gap'' - the worst-case gap between the optimum of a convex relaxation and that of the integer program it approximates - can sometimes be reduced by considering a hierarchy of relaxations derived from lift-and-project methods.
We will look at different hierarchies, and some universal properties of the LP and SDP relaxations derived from them. Moreover, we will see how, for certain NP-hard optimization problems, we can achieve improved approximations using such strengthened relaxations while maintaining polynomial running time overall.

Tuesday, 13:45 - 14:10 h, Room: H 3005, Talk 2

Monique Laurent
Error bounds for sums of squares relaxations of some polynomial optimization problems

Coauthor: Etienne de Klerk

Abstract:
We consider semidefinite programming relaxations for polynomial optimization problems
based on sums of squares of polynomials and the dual relaxations based on moment matrices.
In particular, we discuss error bounds for optimization over the
hypercube for the hierarchy of relaxations corresponding to the Positivstellensätze of
Handelman and of Schmüdgen.
These bounds are explicit and sharpen an earlier result
of Schweighofer (2004).
We also discuss links to error bounds for optimization over the simplex and for the Lasserre hierarchy.

Tuesday, 14:15 - 14:40 h, Room: H 3005, Talk 3

Madhur Tulsiani
Effectiveness and limitations of local constraints

Abstract:
I will give an overview of various hierarchies which strengthen linear and semidefinite programs by adding increasingly larger local constraints. I will discuss some recent techniques for arguing about the quality of approximation achieved by these hierarchies. The focus of the talk will be on lower bounds and connections to other areas like proof complexity.