A combinatorial, primal-dual approach to semidefinite programs

Semidefinite programs (SDP) have been used in many recentapproximation algorithms. We develop a general primal-dualapproach to solve SDPs using a generalization ofthe well-known multiplicative weights update rule to symmetricmatrices. For a number of problems, such as Sparsest Cut and Balanced Separator in undirected and directed weighted graphs, and the Min UnCut problem, this yields combinatorial approximationalgorithms that are significantly more efficient than interiorpoint methods. The design of our primal-dual algorithms is guidedby a robust analysis of rounding algorithms used to obtain integersolutions from fractional ones.

Authors

• Sanjeev Arora
• Satyen Kale

Keywords

• balanced separator
• matrix multiplicative weights
• min UnCut
• semidefinite programming
• sparsest cut