A combinatorial, primal-dual approach to semidefinite programs

Sanjeev Arora, Satyen Kale

Research output: Contribution to journalArticle

11 Scopus citations

Abstract

Semidefinite programs (SDPs) have been used in many recent approximation algorithms. We develop a general primal-dual approach to solve SDPs using a generalization of the well-known multiplicative weights update rule to symmetric matrices. For a number of problems, such as SPARSEST CUT and BALANCED SEPARATOR in undirected and directed weighted graphs, MIN UNCUT and MIN 2CNF DELETION, this yields combinatorial approximation algorithms that are significantly more efficient than interior point methods. The design of our primal-dual algorithms is guided by a robust analysis of rounding algorithms used to obtain integer solutions from fractional ones. Our ideas have proved useful in quantum computing, especially the recent result of Jain et al. [2011] that QIP = PSPACE.

Original languageEnglish (US)
Article number12
JournalJournal of the ACM
Volume63
Issue number2
DOIs
StatePublished - May 2016

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Keywords

  • Combinatorial algorithms
  • Primal-dual approximation algorithms
  • Semidefinite programming

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

  • Cite this