Yioop - PHP Search Engine

2015-05-13

10. Give the APPROX-SUBSET-SUM algorithm from class.

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 >t

7 let zstar be the largest value in L[n]

8 return zstar

TRIM(L, δ)

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

1 let m be the length of L

2 L' = (y[1])

3 last = y[1]

4 for i = 2 to m

5 if y[i] > last * (1 + δ) // y[i] ≥ last because L is sorted

6 append y[i] to L'

7 last = y[i]

8 return L'

Team: Tina Philip, Nayana DV, Sushma.

(Edited: 2015-05-13)

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 >t 7 let zstar be the largest value in L[n] 8 return zstar TRIM(L, δ) We assume L = (y[1], ..., y[m]) 1 let m be the length of L 2 L' = (y[1]) 3 last = y[1] 4 for i = 2 to m 5 if y[i] > last * (1 + δ) // y[i] ≥ last because L is sorted 6 append y[i] to L' 7 last = y[i] 8 return L' Team: Tina Philip, Nayana DV, Sushma.