TY - GEN
T1 - A combinatorial, primal-dual approach to semidefinite programs
AU - Arora, Sanjeev
AU - Kale, Satyen
PY - 2007
Y1 - 2007
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.
KW - Balanced separator
KW - Matrix multiplicative weights
KW - Min UnCut
KW - Semidefinite programming
KW - Sparsest cut
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 -