Approximation Algorithms (3)

Subset-Sum Problem

Subset-Sum Proble/m

• An instance of the subset-sum problem is a pair $(S,t)$
  • $S$ is a positive integer set $\{X_1,X_2,\dots,X_n\}$
  • $t$ is a positive integer
• Whether there exists a subset of $S$ that adds up exactly to the target value $t$
• e.g.)
  • $S=\{1,2,7,14,49,54\},t=58$
  • The subset $S'=\{2,7,49\}$ is a solution

---

Exponential Time Exact Algorithm

Preliminary

• Given a integer set $S$ and a integer $x$
  • $S+x=\{ s+x:s\in S\}$
  • e.g.) $S=\{0,1,5,9\},S+2=\{2,3,7,11\}$
• $P_i$ denote the set of all possible summation values by selecting a subset of $\{x_1,x_2,\dots,x_i\}$
  • e.g.) $S=\{1,4,5\}, P_1=\{0,1\}, P_2=\{0,1,4,5\}, P_3=\{0,1,4,5,6,9,10\}$
  • $P_i=P_{i-1}\cup(P_{i-1}+x_i)$
• $L_i$ denote a sorted list containing every element of $P_i$ whose value is not more than $t$
• $MERGE-LISTS(L,L')$ returns the sorted list that is merge of its two sorted input lists with duplicate values removed
  • Runs in time $O(|L|+|L'|)$

Algorithm

---

Approximation

Fully Polynomial Time Approximation Scheme

• Polynomial in $1/\epsilon$ as well as in the size of the input

---

Trimming

• If two values in $L$ are close, maintain only one value
• To trim a list $L$ by $\delta(0<\delta < 1)$ means
  • For every removed element $y$, there is an element $z$ still in trimming result $L'$ satisfying $\displaystyle{{y}\over{1+\delta}} \leq z \leq y$
• e.g.)
  • $\delta=0.1$
  • $L=<10,11,12,15,20,21,22,23,24,29>$
  • $L'=<10,12,15,20,23,29>$
    • $11$ is represented by $10(11/1.1 \leq 10 \leq 11)$
    • $21,22$ are represented by $20$
    • $24$ is represented by $23$

• Scan $L$ in monotonically increasing order
• If it is the first element of $L$ or
  if it cannot be represented by the most recent number placed into $L'$

---

APPROX-SUBSET-SUM

• Given input $S$, a target integer $t$ and an approximation parameter $\epsilon$
• Return a value $z$ whose value is within a $1+\epsilon$ factor of the optimal solution
  
  

---

Fully polynomial time approximation scheme

• Proof
  • Every element of $L_i$ is a memeber of $P_i$
  • Therefore, the value $z^*$ is the sum of some subset of $S$
  • $y^* \in P_n$ denote an optimal solution
  • $z^* \leq y^*$
  • Need to show
    1. $\displaystyle{{y^*}\over{z^*}} \leq 1+\epsilon$
    2. Running time is polynomial in both $1/\epsilon$ and the size of the input