Skip to main content

A Combinatorial, Primal-Dual Approach to Semidefinite Programs

Author(s): Arora, Sanjeev; Kale, Satyen

To refer to this page use:
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.
Publication Date: 2016
Citation: Arora, Sanjeev, and Satyen Kale. "A combinatorial, primal-dual approach to semidefinite programs." Journal of the ACM 63, no. 2 (2016). doi:10.1145/2837020
DOI: 10.1145/2837020
ISSN: 0004-5411
EISSN: 1557-735X
Type of Material: Journal Article
Journal/Proceeding Title: Journal of the ACM
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.