22
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 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, 2010 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, 2010 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, 2010 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, 2011 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, 2011 at 16:26

3 Answers 3

Reset to default
7
$\begingroup$

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/

Improve this answer
$\endgroup$
1
  • $\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, 2011 at 22:23
4
$\begingroup$

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

Improve this answer
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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