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.

  • 8
    $\begingroup$ 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 and links to several useful references are here. Lovasz has written a general survey of semidefinite programming and combinatorial optimization, but this is not focused on approximation algorithms. $\endgroup$ – arnab Dec 27 '10 at 18:00
  • 1
    $\begingroup$ Thanks Arnab. I guess it never hurts to ask. :) And if there is enough interest around, maybe one could think about writing something surveyish. $\endgroup$ – Michael Dec 27 '10 at 18:12
  • 4
    $\begingroup$ Sorry, my links were mangled above. The first link was to pikomat.mff.cuni.cz/honza/napio/arora.pdf and the second to homepages.cwi.nl/~monique/ow-seminar-sdp and the third to cs.elte.hu/~lovasz/semidef.ps $\endgroup$ – arnab Dec 27 '10 at 18:19
  • $\begingroup$ Added a +50 bounty to see if there are any updates (or people who have started writing surveys) since I posted the question originally. $\endgroup$ – Michael Mar 10 '11 at 21:12
  • 2
    $\begingroup$ Sure, it's not a survey, but I liked very much this course by Sanjeev Arora: mpi-inf.mpg.de/conference/adfocs/material/… $\endgroup$ – Alex Golovnev Dec 15 '11 at 16:26

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/

  • $\begingroup$ 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. $\endgroup$ – Michael Nov 4 '11 at 22:23

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


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.