I was recently going through a survey on semidefinite programming and its use in approximation algorithms. Here are some problems I am familiar with that have SDP approximations:

  1. Max Cut ($\approx 0.878$ approximation)
  2. Approximating Quadratic Programs ($\frac{2}{\pi}$ approximation)
  3. Maximum Correlational Clustering ($0.75$ approximation)
  4. Max 2SAT ($\approx 0.878$ approximation)
  5. Maximum Directed Cut ($\approx 0.79$ approximation)

All these problems happen to be maximisation problems. On the other hand, the only minimisation problem I know that uses SDP is colouring $3-$colourable graphs where SDP gives a $O(n^{0.387})$ approximation.

I am interested in SDPs being used to approximate minimisation problems, and specifically if it has been successfully used to approximate a minimisation problem to within a constant factor.

  • 1
    $\begingroup$ Here is one by Skutella for scheduling. dl.acm.org/doi/abs/10.1145/375827.375840 There are several others as well. $\endgroup$ Jul 15 at 16:58
  • $\begingroup$ @ChandraChekuri Thank you! $\endgroup$ Jul 15 at 17:22
  • 1
    $\begingroup$ A well known and famous result of Arora and Rao and Vazirani shows that an SDP relaxation yields $O(\sqrt{\log n})$-approximation for balanced separators. Although this is not a constant factor approximation, SDP based methods yield strong results for semi-random models. See this paper of Makarychevs and related work. arxiv.org/pdf/1406.5665v1.pdf $\endgroup$ Jul 15 at 19:13

Your Answer

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

Browse other questions tagged or ask your own question.