[Solved]: Proof by induction concerning approximation algorithm for subset sum

Problem Detail: 

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?

Asked By : James the Great

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/44522

3.2K people like this

 Download Related Notes/Documents