Fast Algorithms for Approximate Semide. nite Programming using the Multiplicative Weights Update Method

Semidefinite programming (SDP) relaxations appear in many recent approximation algorithms but the only general technique for solving such SDP relaxations is via interior point methods. We use a Lagrangian-relaxation based technique (modified from the papers of Plotkin, Shmoys, and Tardos (PST), and Klein and Lu) to derive faster algorithms for approximately solving several families of SDP relaxations. The algorithms are based upon some improvements to the PST ideas - which lead to new results even for their framework - as well as improvements in approximate eigenvalue computations by using random sampling.

Authors

• Sanjeev Arora
• Elad Hazan
• Satyen Kale

Keywords

• Approximation algorithms
• Algorithm design and analysis
• Frequency estimation
• Computer science
• Polynomials
• Lagrangian functions
• Eigenvalues and eigenfunctions
• Sampling methods
• Ellipsoids
• NP-hard problem
• Semidefinite Programming
• Multiplicative Weights Update
• Estimation Algorithm
• Interior Point
• Approximate Computation
• Interior Point Method
• Running Time
• Values In The Range
• Unit Vector
• Total Run Time
• Convex Set
• Eigenvalue Problem
• Nonzero Entries
• Positive Semidefinite Matrix
• Positive Semidefinite
• Cholesky Decomposition
• Correlation Clustering
• Binary Search
• Feasibility Problem
• Minimal Distortion
• Multiplicative Update
• Interior-point Algorithm
• Standard Basis Vector
• Number Of Nonzero Entries
• Worst-case Estimate
• Combination Of Constraints