TY - GEN
T1 - Fast algorithms for approximate semidefinite programming using the multiplicative weights update method
AU - Arora, Sanjeev
AU - Hazan, Elad
AU - Kale, Satyen
PY - 2005
Y1 - 2005
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=33748601484&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33748601484&partnerID=8YFLogxK
U2 - 10.1109/SFCS.2005.35
DO - 10.1109/SFCS.2005.35
M3 - Conference contribution
AN - SCOPUS:33748601484
SN - 0769524680
SN - 9780769524689
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 339
EP - 348
BT - Proceedings - 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005
T2 - 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005
Y2 - 23 October 2005 through 25 October 2005
ER -