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


Chair: Konstantinos Georgiou



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

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


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


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


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.


  Online lending company provides a wide range of ways to get money by means of Payday Loans Tennessee. Since its introduction in the market buying Order Cialis can be exclusively in pharmacy chains with a prescription from a doctor. I agree that this is very inconvenient and takes a lot of time and effort.