Abstract:

Semidefinite programming has been widely used in many recent 
approximation algorithms. Unfortunately, solving semidefinite 
programs is not easy (though polynomial-time). This is in contrast 
to linear programming, which can often be replaced by more 
"combinatorial" methods. 

We develop a new, general, primal-dual approach to solve 
semidefinite programs. The approach relies upon a generalization of 
the well-known "multiplicative weights update" rule to symmetric 
matrices that is of independent interest. We obtain the fastest 
known algorithms to obtain approximate solutions to a variety of 
problems such as {\sc Sparsest Cut} and {\sc Balanced Separator} in 
undirected and directed weighted graphs and the {\sc Min-Uncut} 
problem. A side-benefit is that our algorithms are "combinatorial." 

We hope that this work will lead to more practical alternatives to 
semidefinite programming. 

(Joint work with Satyen Kale; to appear in STOC 2007)