Authors
Satyen Kale, Sanjeev Arora
Description
The Multiplicative Weights Update Method Page 1 A Combinatorial, Primal-Dual Approach to
Semidefinite Programs Satyen Kale Microsoft Research Joint work with Sanjeev Arora
Princeton University Page 2 The Ubiquity of Semidefinite Programming Max Cut [GW’95]
Balanced Partitioning [ARV’04] Graph Coloring [KMS’98, ACC’06] (a Ç ¬b) Æ (¬a Ç c) Æ (a Ç b)
Æ (¬c Ç b) Constraint Satisfaction [ACMM’05] 1 0 0 0 1 1 0 1 SDP Control Theory dx(t)/dt = Ax(t)
Page 3 Algorithms for SDP Ellipsoid method [GLS’81]: • O(n8) iterations Interior point methods
[NN’90, A’95]: • O(√m(n3 + m)) time Lagrangian Relaxation [KL’95], [AHK’05]: • Reduction to
eigenvectors • poly(1/ε) dependence on ε, limits applicability (eg Sparsest Cut) A 1 • X ^ b1 # A
m • X ^ bm ∑ i w i (A i • X – bi) ^ 0 Combinatorial, Primal-Dual algorithms Page 4 Primal-Dual
algorithms for LP: Multicommodity Flows Unit capacities Objective: Maximize total flow, …
Scholar articles