1
$\begingroup$

Assignment question

For algorithm APPROX-SUBSET-SUM, prove by induction on $i$ that for every element $y \in P_i$ that is at most the target sum $T$, there is a $z \in L_i$ such that

$$\frac{y}{(1+\frac{\epsilon}{2n})^i} \leq z \leq y$$

Here $\epsilon$ is the relative error bound, $P_i$ is the set of all subset sums of the first $i$ elements in the universe, and $L_i$ is the corresponding discretized set produced by APPROX-SUBSET-SUM.

My thoughts

I understand that proof by induction means that proving something for all natural numbers by first proving that it is true for $0$, and that if it is true for $n$ (or sometimes, for all numbers up to $n$), then it is true also for $n+1$. However, do I simply substitute $0$ and $n+1$ into $n$ and that would solve the question completely?

$\endgroup$
2
  • 1
    $\begingroup$ Note that the notations $P_i,L_i,T$ are not standard, and that APPROX-SUBSET-SUM itself is not standard. I had to guess what all these symbols mean. $\endgroup$ Jul 19, 2015 at 3:58
  • 2
    $\begingroup$ Please make your question self-contained by including the definition of all notation, all variables, and the algorithm APPROX-SUBSET-SUM. $\endgroup$
    – D.W.
    Jul 19, 2015 at 4:43

1 Answer 1

1
$\begingroup$

You haven't described the approximation algorithm, so I assume it's something like the following one (perhaps with a few changes in some details):

  • Input: a universe $U = \{x_1,\ldots,x_n\}$, a target sum $T$, and an accuracy parameter $\epsilon$.
  • Initialize $L_i = \{0\}$.
  • For $i = 1, \ldots, n$:
    • Compute $L_{i+1} = L_i \cup \{\ell + x_i : \ell \in L_i\}$.
    • Remove all element larger than $T$ from $L_{i+1}$.
    • Replace each element $\ell \in L_{i+1}$ by the largest power of $1+\epsilon/2n$ which is at most $\ell$.
  • Return the element in $L_n$ closest to $T$.

This is a $1+O(\epsilon)$-approximation algorithm, in the sense that it can tell whether there is a subset of $U$ summing to roughly $T$, up to a factor of $1+O(\epsilon)$.

The exercise asks you to show that for each $i \in \{0,\ldots,n\}$, the following is true: if $y \in P_i$ (the set of all sums of subsets of $\{x_1,\ldots,x_i\}$) is at most $T$, then there is an element $z \in L_i$ which is approximately equal to $y$, in the sense that $$ \frac{y}{(1+\frac{\epsilon}{2n})^i} \leq z \leq y. $$ Taking $i = n$ will give the desired analysis of the complete algorithm.

Let us denote the claim symbolically by $C_i$. The exercise suggests that this claim can be proved by induction on $i$. This suggests the following plan to prove $C_0,\ldots,C_n$:

  1. Prove $C_0$.
  2. For $i=1,\ldots,n$, assuming $C_{i-1}$ is true, prove that $C_i$ is true.

To find out what claim $C_0$ or $C_{i-1}$ is, you will need to substitute $0$ or $i-1$ for $i$ in the claim.

Good luck with executing this plan.

$\endgroup$
1
  • $\begingroup$ Thanks for your help! Finally got the time to understand it $\endgroup$ Jul 28, 2015 at 17:25

Not the answer you're looking for? Browse other questions tagged or ask your own question.