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


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.


Talk 1 of the invited session Tue.2.H 3005
"Lift-and-project methods for combinatorial optimization problems" [...]
Cluster 2
"Combinatorial optimization" [...]


  The majority of financial loan companies provide the service of getting North Carolina Loans Online for U.S. citizens. But it is worth noting that these tests were carried out on the blood cells. Therefore, it's too early to say about scientific evidence of Viagra influence on blood clots.