CODEWITHSUNDEEP
algorithmapproximation
Belgi
Belgi

Reputation: 15052

Approximation for set cover

I started learning about approximation algorithms, I'm reading a book about that and I don't understand the analysis for the set cover algorithm.

Can someone please explain lemma 2.3 ? it's short but I don't understand it...

http://view.samurajdata.se/psview.php?id=0482e9ff&page=13

Upvotes: 0

Views: 285

Answers (1)

perelman
perelman

Reputation: 1777

The algorithm is assigning a "price" price(e) to each element of the universe U where that price is the cost of the set S used to cover e divided by the number of elements newly covered by the set S (any elements already covered must have been assigned a lower price by a previous set due to the definition of the algorithm).

There exists an optimal solution which chooses a set of sets with total cost OPT. As that solution covers all elements, it certainly covers whatever elements have not yet been covered. Covering the rest of the elements (the set CBar in the notation of the proof) at cost OPT would mean covering each element at cost-effectiveness OPT/|CBar| by the definition of cost-effectiveness (aka price). As the optimal solution contains a set which covers all remaining elements, suppose we pick a set S from the optimal solution which covers at least one remaining element (e_k in lemma 2.3). Note that we are choosing the set with the best cost-effectiveness, so its cost-effectiveness must be at least as good as the average cost-effectiveness of the sets in the optimal solution of OPT/|CBar|.

The last part is that due to the definitions, |CBar|=n-(k-1)=n-k+1 as k-1 elements have already been covered and we are looking at covering element k. Therefore, the cost-effectiveness of S and therefore price(e_k) is bounded by OPT/(n-k+1).

Upvotes: 2

Related Questions