2
$\begingroup$

The inequality is $$ 1 - (1 - x_i)^{\ln{\vert E \vert} + \ln{4}} \leq (\ln{\vert E \vert} +\ln {4})x_i $$

With the following constraints:

  • $\vert E \vert \in \mathbb{N}^+$
  • $x_i \in [0, 1]$.

This appeared during my approximation algorithm class and my professor just gave no explaination on it. Any help is appreciated!

$\endgroup$

2 Answers 2

2
$\begingroup$

You can rewrite this inequality this way: $$ (1-x_i)^{\ln|E| + \ln4} \geq 1-(\ln|E|+\ln4)x_i$$ with $-x_i > -1$ and $\ln|E| + \ln4 >1$. This is true by Bernoulli's inequality

$\endgroup$
1
$\begingroup$

Let us take $a = \ln |E| + \ln 4$. Then the problem is equivalent to

$1 - (1-x)^a \le ax$ or to rearrange it, $(1-x)^a \ge 1- ax$. Please check out Bernoulli's inequality for the rest. There are some conditions for it to hold which are satisfied in this case.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .