A combinatorial, primal-dual approach to semidefinite programs

Sanjeev Arora; Satyen Kale

doi:10.1145/1250790.1250823

A combinatorial, primal-dual approach to semidefinite programs

Sanjeev Arora, Satyen Kale

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

127 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 language	English (US)
Title of host publication	STOC'07
Subtitle of host publication	Proceedings of the 39th Annual ACM Symposium on Theory of Computing
Pages	227-236
Number of pages	10
DOIs	https://doi.org/10.1145/1250790.1250823
State	Published - 2007
Event	STOC'07: 39th Annual ACM Symposium on Theory of Computing - San Diego, CA, United States Duration: Jun 11 2007 → Jun 13 2007

Publication series

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

Other

Other	STOC'07: 39th Annual ACM Symposium on Theory of Computing
Country/Territory	United States
City	San Diego, CA
Period	6/11/07 → 6/13/07

All Science Journal Classification (ASJC) codes

Software

Keywords

Balanced separator
Matrix multiplicative weights
Min UnCut
Semidefinite programming
Sparsest cut

Access to Document

10.1145/1250790.1250823

Cite this

@inproceedings{7daa79fee7f740c4a910b206b942ef1e,

title = "A combinatorial, primal-dual approach to semidefinite programs",

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.",

keywords = "Balanced separator, Matrix multiplicative weights, Min UnCut, Semidefinite programming, Sparsest cut",

author = "Sanjeev Arora and Satyen Kale",

year = "2007",

doi = "10.1145/1250790.1250823",

language = "English (US)",

isbn = "1595936319",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

pages = "227--236",

booktitle = "STOC'07",

note = "STOC'07: 39th Annual ACM Symposium on Theory of Computing ; Conference date: 11-06-2007 Through 13-06-2007",

}

Arora, S & Kale, S 2007, A combinatorial, primal-dual approach to semidefinite programs. in STOC'07: Proceedings of the 39th Annual ACM Symposium on Theory of Computing. Proceedings of the Annual ACM Symposium on Theory of Computing, pp. 227-236, STOC'07: 39th Annual ACM Symposium on Theory of Computing, San Diego, CA, United States, 6/11/07. https://doi.org/10.1145/1250790.1250823

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 -

A combinatorial, primal-dual approach to semidefinite programs

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this