<p>Check Chapter 6 in the book "The Design of Approximation Algorithms" by Williamson and Shmoys. The book is available on-line here: <a href="http://www.designofapproxalgs.com/">http://www.designofapproxalgs.com/</a></p>

CC BY-SA 3.0
2011-11-04T22:23:15.367Z
Thanks. If I recall correctly, the book does not go far beyond what is already written in Vijay Vazirani's book with respect to SDPs. However, chapters 6.4 and 6.5 offer insights into more advanced hyper-plane rounding algorithms; yet it only treats the (standard) uniform case.
Michael
CC BY-SA 3.0
2011-11-04T20:21:25.983Z
2011-11-04T20:21:25.983Z
slimton
<p>There is a nice book by Gartner and Matousek on SDPs and their applications to approximation algorithms. It covers a lot with the added benefit of giving a good introduction to the theory of semi-definite programming. See <a href="http://books.google.com/books/about/Approximation_Algorithms_and_Semidefinit.html?id=5QeLPOvIpNUC" rel="nofollow">http://books.google.com/books/about/Approximation_Algorithms_and_Semidefinit.html?id=5QeLPOvIpNUC</a></p>

CC BY-SA 3.0
2012-09-26T20:13:58.797Z
2012-09-26T20:13:58.797Z
Chandra Chekuri
<p>There's this survey:
<a href="http://ttic.uchicago.edu/~madhurt/Papers/sdpchapter.pdf" rel="nofollow">http://ttic.uchicago.edu/~madhurt/Papers/sdpchapter.pdf</a>
which has a focus on the hierarchies of convex programming. It has Max-Cut, Sparsest-Cut, coloring, hypergraph independent set, knapsack.</p>

CC BY-SA 3.0
2012-09-26T18:51:30.860Z
2012-09-26T18:51:30.860Z
Dana Moshkovitz
<p>When designing approximation algorithms one sometimes solves a semidefinite program followed by a rounding step. An often used example to illustrate this is Max-Cut. (See e.g. Approximation Algorithms by Vijay Vazirani.)</p>

<p>Are there good educational sources or surveys going beyond the Max-Cut problem to explain more complex rounding algorithms and techniques used for their analysis? I'm thinking of cases when the vectors of the SDP-solution aren't distributed uniformly on a hypersphere, they have different lengths, or have other properties making the analysis harder.</p>

CC BY-SA 2.5
2010-12-27T18:00:41.360Z
I think you aren't getting any answers, because there really aren't any good surveys around on rounding SDP's :) Sanjeev Arora has given a survey talk on the subject at various places; his slides are [here](http://pikomat.mff.cuni.cz/honza/napio/arora.pdf) and links to several useful references are [here](http://homepages.cwi.nl/~monique/ow-seminar-sdp/).  Lovasz has written [a general survey](http://www.cs.elte.hu/~lovasz/semidef.ps) of semidefinite programming and combinatorial optimization, but this is not focused on approximation algorithms.
arnab
CC BY-SA 2.5
2010-12-27T18:12:07.743Z
Thanks Arnab. I guess it never hurts to ask. :) And if there is enough interest around, maybe one could think about writing something surveyish.
Michael
CC BY-SA 2.5
2010-12-27T18:19:35.813Z
Sorry, my links were mangled above. The first link was to http://pikomat.mff.cuni.cz/honza/napio/arora.pdf and the second to http://homepages.cwi.nl/~monique/ow-seminar-sdp and the third to http://cs.elte.hu/~lovasz/semidef.ps
arnab
CC BY-SA 2.5
2011-03-10T21:12:35.277Z
Added a +50 bounty to see if there are any updates (or people who have started writing surveys) since I posted the question originally.
Michael
CC BY-SA 3.0
2011-12-15T16:26:38.683Z
Sure, it's not a survey, but I liked very much this course by Sanjeev Arora: http://www.mpi-inf.mpg.de/conference/adfocs/material/ADFOCS%202011%20Lectures%20and%20Exercises.zip
Alex Golovnev
CC BY-SA 3.0
2011-12-15T19:31:59.960Z
Thanks for the pointer Alex. I wished the slides weren't only provided in the proprietary formats ppt and pptx though.
Michael
<ds.algorithms><reference-request><approximation-algorithms><semidefinite-programming><csp>
Educational Source or Survey on Analysis of Semidefinite Program?
Michael
# Educational Source or Survey on Analysis of Semidefinite Program?

(Asked by: username_0 on 2010-12-27)

When designing approximation algorithms one sometimes solves a semidefinite program followed by a rounding step. An often used example to illustrate this is Max-Cut. (See e.g. Approximation Algorithms by Vijay Vazirani.)

Are there good educational sources or surveys going beyond the Max-Cut problem to explain more complex rounding algorithms and techniques used for their analysis? I'm thinking of cases when the vectors of the SDP-solution aren't distributed uniformly on a hypersphere, they have different lengths, or have other properties making the analysis harder.

**Tags:** ds.algorithms, reference-request, approximation-algorithms, semidefinite-programming, csp

> **Comments:**
> **username_1**: I think you aren't getting any answers, because there really aren't any good surveys around on rounding SDP's :) Sanjeev Arora has given a survey talk on the subject at various places; his slides are [here](http://pikomat.mff.cuni.cz/honza/napio/arora.pdf) and links to several useful references are [here](http://homepages.cwi.nl/~monique/ow-seminar-sdp/).  Lovasz has written [a general survey](http://www.cs.elte.hu/~lovasz/semidef.ps) of semidefinite programming and combinatorial optimization, but this is not focused on approximation algorithms.  
> **username_0**: Thanks Arnab. I guess it never hurts to ask. :) And if there is enough interest around, maybe one could think about writing something surveyish.  
> **username_1**: Sorry, my links were mangled above. The first link was to http://pikomat.mff.cuni.cz/honza/napio/arora.pdf and the second to http://homepages.cwi.nl/~monique/ow-seminar-sdp and the third to http://cs.elte.hu/~lovasz/semidef.ps  
> **username_0**: Added a +50 bounty to see if there are any updates (or people who have started writing surveys) since I posted the question originally.  
> **username_2**: Sure, it's not a survey, but I liked very much this course by Sanjeev Arora: http://www.mpi-inf.mpg.de/conference/adfocs/material/ADFOCS%202011%20Lectures%20and%20Exercises.zip  
> **username_0**: Thanks for the pointer Alex. I wished the slides weren't only provided in the proprietary formats ppt and pptx though.  

---

## 3 answers

### Answer by username_3 on 2011-11-04. Score: 7

Check Chapter 6 in the book "The Design of Approximation Algorithms" by Williamson and Shmoys. The book is available on-line here: <http://www.designofapproxalgs.com/>

> **Comments:**
> **username_0**: Thanks. If I recall correctly, the book does not go far beyond what is already written in Vijay Vazirani's book with respect to SDPs. However, chapters 6.4 and 6.5 offer insights into more advanced hyper-plane rounding algorithms; yet it only treats the (standard) uniform case.  

---

### Answer by username_4 on 2012-09-26. Score: 4

There is a nice book by Gartner and Matousek on SDPs and their applications to approximation algorithms. It covers a lot with the added benefit of giving a good introduction to the theory of semi-definite programming. See <http://books.google.com/books/about/Approximation_Algorithms_and_Semidefinit.html?id=5QeLPOvIpNUC>


---

### Answer by username_5 on 2012-09-26. Score: 2

There's this survey:
<http://ttic.uchicago.edu/~madhurt/Papers/sdpchapter.pdf>
which has a focus on the hierarchies of convex programming. It has Max-Cut, Sparsest-Cut, coloring, hypergraph independent set, knapsack.


---

