2
$\begingroup$

The background is from a highly cited paper "Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming".

I know how to prove $\frac{2\theta}{\pi}\ge \rho(1-\cos \theta)$ for $\theta\in [0, \pi]$, where $\rho=0.87856$.

But I get stuck in the proof of a related inequality $2-\frac{2\theta}{\pi}\ge \rho(1+\cos \theta)$ for $\theta\in [0, \pi]$?

  • 0
    Look at the page 1122 of the paper www-math.mit.edu/~goemans/PAPERS/maxcut-jacm.pdf2011-06-29

2 Answers 2

3

If you take $\frac{ 2 \theta }{ \pi } \geq \rho (1-\cos\theta)$ as given, and observe that $ \cos(\theta) = -\cos(\pi - \theta) $ for $\theta \in [0,\pi]$, you just substitute $\pi-\theta$ for $\theta$ in the original equation to get: \begin{align} \frac{ 2 (\pi-\theta) }{ \pi } &\geq \rho (1-\cos(\pi-\theta)) \\ 2 - \frac{ 2 \theta }{ \pi } &\geq \rho (1+\cos\theta) \end{align}

  • 0
    That is just what I am looking for.2011-06-29
2

So you can do a true brute force attack on it. Create the function $g(\theta ) := 2 - \frac{2 \theta }{\pi} - \rho (1 + \cos \theta)$. It's continuous. Take the derivative and find the minimum on $[0, \pi ]$. You'll find $g \geq 0$, which is what you wanted.

So I just did it on W|A. But are you looking for a better way to do it? Something more witty?

  • 0
    Look at the page 1122 of the paper http://www-math.mit.edu/~goemans/PAPERS/ma$x$cut-jacm.pdf2011-06-29