<p>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:</p>
<ol>
<li>Max Cut (<span class="math-container">$\approx 0.878$</span> approximation)</li>
<li>Approximating Quadratic Programs (<span class="math-container">$\frac{2}{\pi}$</span> approximation)</li>
<li>Maximum Correlational Clustering (<span class="math-container">$0.75$</span> approximation)</li>
<li>Max 2SAT (<span class="math-container">$\approx 0.878$</span> approximation)</li>
<li>Maximum Directed Cut (<span class="math-container">$\approx 0.79$</span> approximation)</li>
</ol>
<p>All these problems happen to be <strong>maximisation problems</strong>. On the other hand, the only minimisation problem I know that uses SDP is colouring <span class="math-container">$3-$</span>colourable graphs where SDP gives a <span class="math-container">$O(n^{0.387})$</span> approximation.</p>
<p>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.</p>

CC BY-SA 4.0
2021-07-15T16:58:30.297Z
Here is one by Skutella for scheduling. https://dl.acm.org/doi/abs/10.1145/375827.375840 There are several others as well.
Chandra Chekuri
CC BY-SA 4.0
2021-07-15T19:13:40.123Z
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. https://arxiv.org/pdf/1406.5665v1.pdf
Chandra Chekuri
<approximation-algorithms><optimization><semidefinite-programming>
Examples of SDP constant approximation algorithms on minimisation problems
user3508551
# Examples of SDP constant approximation algorithms on minimisation problems

(Asked by: username_0 on 2021-07-15)

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.

**Tags:** approximation-algorithms, optimization, semidefinite-programming
> **Comments:**
> **username_1**: Here is one by Skutella for scheduling. https://dl.acm.org/doi/abs/10.1145/375827.375840 There are several others as well.  
> **username_1**: 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. https://arxiv.org/pdf/1406.5665v1.pdf  

---

## 0 answers

