CS170: Efﬁcient Algorithms and Intractable Problems
October 21, 2013
Lecturer: Satish Rao
Scribe: Amy Boone
1 Set Cover
items: B = f1;:::;ng
sets: S ;:::;S ▯ B
We want to ﬁnd the fewest sets that will cover B. Algorithm:
1. Choose set S that has largest number of elements
2. Remove elements in S fiom all other sets
Property: set cover of size k (best solution) ) a set contaiksof the remaining elements.
ntelements remain at time t (after t sets)
an iteration t, covek ntremaining elements
nt+1 ▯ n t n = (t ▯ )n 1 t
1 t k
nt▯ (1 ▯ ) k ! 0hen do we stop?
remember: (1 ▯ x) ▯ e ▯x so
1 t ▯ 1 t ▯ t
nt▯ (1 ▯ ) k < (e k) n ▯ (e k )n ! t = k lnn
No elements are uncovered? But it still runs in k lnn time instead of k time.
2 Dynamic Programming
Dynamic programming: deﬁne a set of subproblems, order them so each subproblem can be solved using
solutions to previous subproblems. Very similar to recursion. All can be seen as