46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05) Fast Algorithms for Approximate Semide.nite Programming using the Multiplicative Weights Update Method Pittsburgh, Pennsylvania, USA October 23-October 25 ISBN: 0-7695-2468-0
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.35
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.
Citation:
Sanjeev Arora, Elad Hazan, Satyen Kale, "Fast Algorithms for Approximate Semide.nite Programming using the Multiplicative Weights Update Method," focs, pp.339-348, 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05), 2005 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb