Take the 2-minute tour ×
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.

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|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 www-math.mit.edu/~goemans/PAPERS/maxcut-jacm.pdf –  Sunni Jun 29 '11 at 20:33
add comment

2 Answers

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|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
add comment

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|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 www-math.mit.edu/~goemans/PAPERS/maxcut-jacm.pdf –  Sunni Jun 29 '11 at 20:26
add comment

Your Answer

 
discard

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.