0
$\begingroup$

In the problem, we are given a set of clauses, and we want to find an assignment that satisfies as many of them as possible.

1 Answers 1

0

You can expand the brackets that will give you $m - \sum_{j=1}^{m}(\frac{1}{2})^{k_j}$. Now using the fact that $k_j \geq 1$ you can show that $(\frac{1}{2})^{k_j} \leq \frac{1}{2}$. Upper bound each term in the sum and you will obtain the desired inequality.

  • 0
    well, since each $(\frac{1}{2})^{k_j} \leq \frac{1}{2}$ then $\sum_{j=1}^{m}(\frac{1}{2})^{k_j} \leq \sum_{j=1}^{m}\frac{1}{2} \leq \frac{m}{2}$2012-12-03