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 deal is that Indiana Payday Loans online can save your time, nerves and make a solution of all your financial problems. Cialis Professional online is capableto release you reliably from the erection problems, its improved formula gives the new properties to the drug.