Set Cover Problem Overview
Explore the Set Cover Problem, a fundamental question in computer science, operations research, combinatorics, and complexity theory. Learn about its significance, NP-completeness, optimization challenges, and greedy algorithm solutions for efficient set covering.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Set Cover Problem CS 6310 Advanced Design and Analysis of Algorithms Rajani Pingili
The set cover problem is well-known and classical question of in computer science, operations research, combinatorics, and complexity theory. It is one of Karp's 21 popular NP- complete problems. It is a problem "whose study has led to the development of fundamental techniques for the entire field" of approximation algorithms Set Cover Problem
Set Cover Problem Set Cover Problem The Set Cover problem: We have a universe of elements ? = ??, ,?? We have a collection of subsets of ?, ? = ??, ,?? Given a universe ? and a family ? of subsets of ?,a cover is a subfamily ? ? of sets whose union is ?. (?, S) is the input pair and k is an integer in the set covering decision problem; whether there is a set covering of size k or less. This problem is NP-Complete (?, S) is the input pair in the set covering optimization problem and the task is to find a set covering that utilizes the fewest sets. This problem is NP-Hard.
Set Cover Problem Example Set Cover Problem Example Given a set of elements {1,2, .,n} (called the universe) and a collection of S of m sets whose union equals the universe. The set cover problem is to identify the smallest sub- collection of S whose union equals the universe. U = {1,2,3,4,5} and the collection of sets S = {{1,2,3},{2,4},{3,4},{4,5}}. U = Union of S Smaller number of sets: {{1,2,3}, {4,5}}
Greedy Algorithm Greedy Algorithm Rule of greedy algorithm for polynomial time is at each stage, choose the set that contains the largest number of uncovered elements. Approximation ratio H(s), s is the size of the sets to be covered. 1 ? ln n + 1 H(n) is the ?? harmonic number, H(n) = 1 ? ?
Universe U: 2(?+1)- 2 elements The set system consists of k pairwise disjoint sets ?1, , ??with sizes 2,4,8, ., 2?respectively, as well as two disjoint sets ?0, ?1, each of which contains half of the elements of U. Approx. ratio = k/2 = O(log n), since the obtained solution contains the k sets ?1, , ??, while the optimal solution consists only of ?0and ?1. Approximation ratio: Standard Example ln ? lnln? + ?(1) with a tighter analysis of the greedy algorithm [2].
Content 1. http://en.wikipedia.org/wiki/Set_cov er_problem. Slav k Petr A tight analysis of the greedy algorithm for set cover. STOC'96, Pages 435-441, doi:10.1145/237814.237991 2. References
