# Examples of SDP constant approximation algorithms on minimisation problems

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.

• Here is one by Skutella for scheduling. dl.acm.org/doi/abs/10.1145/375827.375840 There are several others as well. Jul 15 at 16:58
• @ChandraChekuri Thank you! Jul 15 at 17:22
• 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 Jul 15 at 19:13