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

 

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.

 
  There are three major facts that should be watched out for in all payday loans in the United States. In this section we give only a brief summary recommendation for admission of Cheap Levitra. Full information can be found in the instructions for receiving medications with vardenafil.