Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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]$?

share|cite|improve this question
From where does the constant $\rho$ come? – Beni Bogosel Jun 29 '11 at 20:18
Look at the page 1122 of the paper – Sunni Jun 29 '11 at 20:33
up vote 3 down vote accepted

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}

share|cite|improve this answer
The derivative of a quotient makes it much more complicated.... – Sunni Jun 29 '11 at 20:29
Oh, there's a much easier way to get the second inequality from the first. – trutheality Jun 29 '11 at 20:50
That is just what I am looking for. – Sunni Jun 29 '11 at 21:02

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?

share|cite|improve this answer
+1. Yes, I am looking for a better way to do it. – Sunni Jun 29 '11 at 20:21
@Sunni: what does your proof of the first inequality look like? – mixedmath Jun 29 '11 at 20:22
Look at the page 1122 of the paper – Sunni Jun 29 '11 at 20:26

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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