A combinatorial, primal-dual approach to semidefinite programs

By Sanjeev Arora, Satyen Kale. Symposium on the Theory of Computing, 2007

295 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Numerical Analysis

View Paper: https://www.semanticscholar.org/paper/488c9b8b8d192acdb6fd264dcd48d648979d3247

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Numerical Analysis

Citations in the corpus

A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization (2015, methodology): “Since our focus is on polynomial time algorithms, we do not discuss pseudo-polynomial algorithms such as the spectral bundle methods [46], multiplicative weight update methods [5], [6], [56], [2], etc.”
The Multiplicative Weights Update Method: a Meta-Algorithm and Applications (2012, methodology): “More recently Arora and Kale [5] have designed a new approach for solving SDPs that involves a variant of the multiplicative update rule at the matrix level; see Section 5 for details.”
Expander flows, geometric embeddings and graph partitioning (2009, unknown): “Recently a more general primal-dual framework was invented [Arora and Kale 2007] for replacing SDPs with faster approximation algorithms for problems other than SPARSEST CUT.”
Spectral Graph Theory (2012, background): “Fast variants of these algorithms may be found in [35, 36, 37, 38, 39].”
Follow the Compressed Leader: Faster Online Learning of Eigenvectors and Faster MMWU (2017, methodology): “Its natural matrix extension, matrix-multiplicative-weight-update (MMWU) [27], has been used towards efficient algorithms for solving semidefinite programs [3, 10, 30], balanced separators [28], Ramanujan sparsifiers [7, 23], and even in the proof of QIP = PSPACE [20].”
Dropping Convexity for Faster Semi-definite Optimization (2015, methodology): “Improvements upon this matter can be found in Arora and Kale (2007) where a primal-dual Multiplicative Weights Update scheme is proposed.”
Statistical properties of community structure in large social and information networks (2008, background): “This paper sparked a flurry of theoretical research on a family of closely related algorithms including [15, 98, 16], all of which can be informally described as combinations of spectral and flow-based techniques which exploit their complementary strengths.”
A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning (2008, methodology): “O( √ logn) through semi-deﬁnite programming. Faster algorithms obtaining similar guarantees have been constructed by Arora, Hazan and Kale [AHK04], Khandekar, Rao and Vazirani [KRV06], Arora and Kale [AK07], and Orecchia, Schulman, Vazirani, and Vishnoi [OSVV08]. 4 2.1 The Algorithm Nibble The algor”
Quantum machine learning: a classical perspective (2017, methodology): “Based on a classical algorithm to solve SDPs by Arora & Kale [108], which has a runtime of Õ(nms(Rr/ )4 + ns(Rr/ )7), where r is an upper bound on the sum of the entries of the optimal solution to the dual problem, in 2016 Brandão & Svore [109] developed a quantum algorithm for SDPs that is quadrati”
Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters (2008, background): “This paper sparked a flurry of theoretical research on a family of closely related algorithms including [15, 99, 16], all of which can be informally described as combinations of spectral and flow-based techniques which exploit their complementary strengths.”