TY - GEN

T1 - A combinatorial, primal-dual approach to semidefinite programs

AU - Arora, Sanjeev

AU - Kale, Satyen

PY - 2007/10/30

Y1 - 2007/10/30

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=35448978697&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=35448978697&partnerID=8YFLogxK

U2 - 10.1145/1250790.1250823

DO - 10.1145/1250790.1250823

M3 - Conference contribution

AN - SCOPUS:35448978697

SN - 1595936319

SN - 9781595936318

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 227

EP - 236

BT - STOC'07

T2 - STOC'07: 39th Annual ACM Symposium on Theory of Computing

Y2 - 11 June 2007 through 13 June 2007

ER -