Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, November 25, 2010, 12:15 pm
Duration: This information is not available in the database
Location: CAB G51
Speaker: Bernd Gärtner
You may know that semidefinite programs can be solved in polynomial time. I will start by pointing out that this is not true. The best you can get in the Turing machine model is a solution with small absolute error, under favorable assumptions on the input (that are valid in many applications). This is done by the ellipsoid method.
Then I will sketch Hazan's simple and practically efficient algorithm in the real RAM model that solves semidefinite programs with a trace-1 constraint up to small relative error in polynomial time.
Automatic MiSe System Software Version 1.4803M | admin login