Yioop - PHP Search Engine

2015-05-13

Practise Final- Question 10.

Submitted by - Divya Kathiravan, Nirav Patel, Yashi Kamboj

Our approximation algorithm for subset sum takes as input a set S={x[1],...,x[n]} of integers (in arbitrary order), a target t and an "approximation parameter" ε where 0<ε<1. It returns a value z whose value is within a 1+ε factor of the optimal solution.

APPROX-SUBSET-SUM(S, t, ε)

1. n = |S| 2. L[0] = (0) 3. for i = 1 to n 4. L[i] = MERGE-LISTS(L[i-1], L[i-1] + x[i]) 5 L[i] = TRIM(L[i], ε/2n) 6 remove from L[i] every element that is greater than t 7 let zstar be the largest value in L[n] 8 return zstar

Trim(L,) We shal assume that L =(y[1],.....,y[m])

         m= length of L
          L’ = y[1]
          last = y[1]
           for i =2 to m

if y[i]>last * (1 + ) //y[i]>= last because L is sorted Append y[i] to L last = y[i] return L’

(Edited: 2015-05-13)

Submitted by - Divya Kathiravan, Nirav Patel, Yashi Kamboj Our approximation algorithm for subset sum takes as input a set S={x[1],...,x[n]} of integers (in arbitrary order), a target t and an "approximation parameter" ε where 0<ε<1. It returns a value z whose value is within a 1+ε factor of the optimal solution. APPROX-SUBSET-SUM(S, t, ε) 1. n = |S| 2. L[0] = (0) 3. for i = 1 to n 4. L[i] = MERGE-LISTS(L[i-1], L[i-1] + x[i]) 5 L[i] = TRIM(L[i], ε/2n) 6 remove from L[i] every element that is greater than t 7 let zstar be the largest value in L[n] 8 return zstar Trim(L,) We shal assume that L =(y[1],.....,y[m]) m= length of L L’ = y[1] last = y[1] for i =2 to m if y[i]>last * (1 + ) //y[i]>= last because L is sorted Append y[i] to L last = y[i] return L’