A combinatorial, primal-dual approach to semidefinite programs

Sanjeev Arora, Satyen Kale

Research output: Chapter in Book/Report/Conference proceedingConference contribution

117 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationSTOC'07
Subtitle of host publicationProceedings of the 39th Annual ACM Symposium on Theory of Computing
Pages227-236
Number of pages10
DOIs
StatePublished - 2007
EventSTOC'07: 39th Annual ACM Symposium on Theory of Computing - San Diego, CA, United States
Duration: Jun 11 2007Jun 13 2007

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

OtherSTOC'07: 39th Annual ACM Symposium on Theory of Computing
Country/TerritoryUnited States
CitySan Diego, CA
Period6/11/076/13/07

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Balanced separator
  • Matrix multiplicative weights
  • Min UnCut
  • Semidefinite programming
  • Sparsest cut

Fingerprint

Dive into the research topics of 'A combinatorial, primal-dual approach to semidefinite programs'. Together they form a unique fingerprint.

Cite this