0

In the analysis of the Cheriton-Tarjan MST algortihm, there is a step that asks to optimize a quantity subject to a nonlinear constraint. Specifically, it's as follows:

Let $c_1, c_2, ..., c_p$ be positive real numbers. Maximize $$\sum_{i=1}^{p}{c_i}$$ subject to $$\sum_{i=1}^p{2^{c_i}} \le 2n$$

The claim is that this sum is maximized at $p (\log_2 \frac{n}{p} + 1)$ when each $c_i$ is $\log_2 \frac{n}{p} + 1$.

Intuitively, this makes sense, but I have no idea how I'd actually go about proving this. How might I approach proving this?

Thanks!

templatetypedef
  • 10,206

1 Answers1

1

Maximising $\sum c_i$ is the same as maximising $2^{\sum c_i} = \prod 2^{c_i}$ as $2^x$ is an increasing function. Now by AM-GM we have:

$$\sqrt[p]{\prod_{i=1}^p 2^{c_i}} \le \frac1p \sum_{i=1}^p 2^{c_i} \le \frac{2n}p \implies \prod_{i=1}^p 2^{c_i} \le \left(\frac{2n}p \right)^p $$

with equality only when all the terms are equal, i.e. when every $c_i = c = 1+ \log_2 \dfrac{n}p$. The maximum of $\sum c_i$ is then of course $p\left(\log_2 \dfrac{n}p + 1\right)$.

Macavity
  • 46,381