0
$\begingroup$

I'm currently reading the book "The Design of Approximation Algorithms". In page 25, they introduce Fact 1.10 and use this to prove Theorem 1.1. Below stated is Fact 1.10.

Fact 1.10 Given positive numbers $a_1,\ldots,a_k$ and $b_1,\ldots,b_k$, then $$\min_{1 \leq i \leq k} \left( \frac{a_i}{b_i} \right) \leq \frac{\sum_{i=1}^k a_i}{\sum_{i=1}^k b_i}.$$

They said you can prove the statement using easy algebraic manipulations. I tried to prove it but I didn't manage. Am I missing something easy here ?

$\endgroup$
0
$\begingroup$

If $\frac ab \leq \frac cd$ then $\frac{a+c}{b+d}$ lies between these two fractions (equal to both if they are equal). To see this, note that

$a(b+d) = ab+ad \leq ab+bc \leq b(a+c)$ , and

$c(b+d) = cb+cd \geq ad+cd \geq d(a+c)$.

Now, suppose you have $\dfrac{\sum a_i}{\sum b_i}$. WLOG, assume that $\frac{a_i}{b_i} \leq \frac{a_j}{b_j}$ if $i < j$. (This is just an ordering, it won't affect the final result.)

Since $\frac{a_2}{b_2} \geq \frac{a_1}{b_1}$, we see that $\frac{a_2 + a_1}{b_2 + b_1} \geq \frac {a_1}{b_1}$.

Since $\frac {a_3}{b_3} \geq \frac{a_2}{b_2} \geq \frac{a_2 + a_1}{b_2+b_1}$, hence $\frac{a_3+a_2+a_1}{b_3+b_2+b_1} \geq \frac{a_2+a_1}{b_2+b_1} \geq \frac{a_1}{b_1}$.

Going this way, you get the result for any index.

$\endgroup$
  • $\begingroup$ nice 1! thanks! $\endgroup$ – user394255 Apr 8 '17 at 10:35
  • $\begingroup$ You are welcome. WLOG is a very powerful notion, it can induce a change in perspective, as I did here (and the inequality is very simple, as you can see). $\endgroup$ – астон вілла олоф мэллбэрг Apr 8 '17 at 10:36
0
$\begingroup$

Note that :

$$ \sum_{i=1}^{k} a_i = \sum_{i=1}^{k} b_i \Big( \frac{a_i}{b_i} \Big) $$

Given that the $b_i$ are positive and:

$$ \forall i \in \lbrace 1, \ldots, k \rbrace, \frac{a_i}{b_i} \geq \min \limits_{1 \leq s \leq k}\Big( \frac{a_s}{b_s} \Big) $$

you obtain:

$$ \sum_{i=1}^{k} a_i \geq \min \limits_{1 \leq s \leq k}\Big( \frac{a_s}{b_s} \Big)\Big( \sum_{i=1}^{k} b_i \Big). $$

$\endgroup$
  • $\begingroup$ thanks! $\phantom{testestss}$ $\endgroup$ – user394255 Apr 8 '17 at 10:25
0
$\begingroup$

A remark that gives an intuitive meaning about the inequality and could be turned into a proof (using a result on convex hulls).

Let us associate to $(a_k,b_k)$ complex number $a_k+ib_k=r_ke^{i\theta_k}$.

Their center of gravity is $\tfrac{1}{n}\left(\sum_{k=1}^k a_k + i \sum_{k=1}^k b_k\right)=re^{i\theta}$.

The given inequality asserts that $\min \tan{\theta_k} \leq \tan{\theta}$, which is equivalent, because $\tan$ is an increasing function, to:

$$\min \theta_k \leq \theta$$

which is graphically evident, and can be proven in a rigorous way (using the concept of convex hull).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy