Fast algorithms for approximate semidefinite programming using the multiplicative weights update method
Authors:
- 1 January 2005
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 339-348
Abstract
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.Keywords
This publication has 22 references indexed in Scilit:
- Approximation Algorithms for Mixed Fractional Packing and Covering Problems2006
- HAPLOFREQ – Estimating Haplotype Frequencies EfficientlyLecture Notes in Computer Science, 2005
- Faster and simpler algorithms for multicommodity flow and other fractional packing problems2002
- Approximating Fractional Multicommodity Flow Independent of the Number of CommoditiesSIAM Journal on Discrete Mathematics, 2000
- Efficient approximation algorithms for semidefinite programs arising from MAX CUT and COLORING1996
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programmingJournal of the ACM, 1995
- The geometry of graphs and some of its algorithmic applicationsCombinatorica, 1995
- Faster Approximation Algorithms For the Unit Capacity Concurrent Flow Problem with Applications to Routing and Finding Sparse CutsSIAM Journal on Computing, 1994
- Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random StartSIAM Journal on Matrix Analysis and Applications, 1992
- Geometric Algorithms and Combinatorial Optimization1988