Advanced Algorithms: ln(n) Approximation for Set Cover Problem
Explore the ln(n) approximation algorithm for the Set Cover problem in advanced algorithms. Learn about the greedy algorithm, guarantees on solution quality, and the quest for near-optimal solutions in this NP-complete conundrum.
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
CMPT 409/815 Advanced Algorithms September 23, 2020
Announcements First assignment is online. Submit your solutions to Coursys by October 7, 2020
Plan for today ln(n) approximation for Set Cover log(n)/n approximation for Max Clique
ln(n) approximation for Set Cover
ln(n) approximation for Set Cover Input: A universe of n elements {a1 an}, and S1 Sm- m subsets of {a1 an} Output: Find a smallest collection of sets that cover all elements {a1 an}
ln(n) approximation for Set Cover Input: A universe of n elements {a1 an}, and S1 Sm- m subsets of {a1 an} Output: Find a smallest collection of sets that cover all elements {a1 an} Fact: The problem of finding a smallest collection is NP-complete In particular, we don t know a polynomial time algorithm solving this problem. and we don t believe there exists a polynomial time algorithm for this problem. We can ask for an almost optimal solution. Goal : Design a poly-time algorithm that outputs a solution that is close to OPT?
ln(n) approximation for Set Cover Input: A universe of n elements {a1 an}, and S1 Sm- m subsets of {a1 an} Output: Find a smallest collection of sets that cover all elements {a1 an} Greedy Algorithm: 1. Let C = empty set // elements covered so far 2. Let SOL = empty set What is the runtime of the algorithm? 3. While C U do find Si SOL such that Sicovers maximal number of points in U\C Add Sito SOL Add the elements of Sito C 4. Return SOL
ln(n) approximation for Set Cover Input: A universe of n elements {a1 an}, and S1 Sm - m subsets of {a1 an} Output: Find a smallest collection of sets that cover all elements {a1 an} What can we guarantee about the quality of the solution? Theorem: If there are k sets that cover all elements, then the algorithm returns at most k ln(n) sets that cover all elements. That is, our greedy algorithm is a ln(n) approximation algorithm for Set Cover.
ln(n) approximation for Set Cover Theorem: If there are k sets that cover all elements, then the algorithm returns at most k ln(n) sets that cover all elements. Proof: Suppose there are k sets that cover all n elements. Then one of the sets must be of size at least n/k. Therefore, since in the first step we pick the largest set, we cover at least n/k elements in the first step. So after the first step we have at most n-n/k = (1-1/k)n elements left. The optimal set cover consists of k sets. Hence, there is a set that covers at least 1/k fraction on the remaining elements, i.e., at least 1/k* (1-1/k)n elements. Therefore, after two steps we are left with at most (1-1/k)* (1-1/k)n elements.
ln(n) approximation for Set Cover Proof cont: After the first step we have at most n-n/k = (1-1/k)n elements left. The optimal set cover (still) consists of k sets. Hence, there is a set that covers at least 1/k fraction on the remaining elements, i.e., at least 1/k* (1-1/k)n elements. Therefore, after two steps the number of elements left is at most (1-1/k)* (1-1/k)n = (1-1/k)2n. After three steps the number of elements left is at most (1-1/k)3n, and so on After t steps the number of elements left is at most (1-1/k)tn, and so on
ln(n) approximation for Set Cover Proof cont: After t steps the number of elements left is at most (1-1/k)tn, and so on Consider the algorithm after t = k ln(n) steps. Then the number of elements left not covered after t = k ln(n) steps is at most (1-1/k)tn = (1-1/k)k ln(n)*n < e-ln(n)n = 1. [using the fact that (1-1/k)k < 1/e for all k>1] Conclusion: after t = k ln(n) steps the number of elements left is less than 1, and therefore, all elements are already covered.
ln(n) approximation for Set Cover Input: A universe of n elements {a1 an}, and S1 Sm - m subsets of {a1 an} Output: Find a smallest collection of sets that cover all elements {a1 an} Greedy Algorithm: 1. Let C = empty set // elements covered so far 2. Let SOL = empty set 3. While C U do find Si SOL such that Si covers maximal number of points in U\C Add Si to SOL Add the elements of Si to C 4. Return SOL
ln(n) approximation for Set Cover Remarks: This algorithms is essentially optimal Theorem: For all >0 it is NP-hard to find a (1- )*ln(n) approximation.
Questions? Comments?
log(n)/n approximation for Max Clique
log(n)/n approximation for Max Clique Input: A graph G = (V,E) on n vertices Goal: Find a clique in G of maximum size.
log(n)/n approximation for Max Clique Input: A graph G = (V,E) on n vertices Goal: Find a clique in G of maximum size. Fact: The problem of finding a maximum clique is NP-complete What about an almost optimal solution? Theorem: For any constant >0 it is NP-hard to find an -approximation for Max-Clique. For example, if G contains a clique of size k=n0.9, it is NP-hard to find a clique of size k/100 Theorem: Given a graph on n vertices that has a clique of size n0.99, it is NP- hard to find a clique of size n0.01
log(n)/n approximation for Max Clique Theorem: There exists a poly time log(n)/n-approximation algorithm for Max- Clique. That is, if a graph contains a clique of size k, then the algorithm outputs a clique of size at least k log(n)/n. For example: if G has a clique of size n/10, the algorithm will find a clique of size > log(n)/10. For which values of k is this algorithm interesting? In HW2: you will design an algorithm that given G that has a clique of size n/log2(n), will find a clique of size > log(n)/log log(n).
log(n)/n approximation for Max Clique Theorem: There exists a poly time log(n)/n-approximation algorithm for Max- Clique. Algorithm: 1. Partition V into t=n/log(n) sets each of size log(n). 2. That is V = V1 V2 Vt for t=n/log(n) 3. In each Vi find a maximal clique using brute force 4. Output the maximal clique found in step 3. What is the runtime of the algorithm?
log(n)/n approximation for Max Clique Theorem: There is a polytime log(n)/n-approximation algorithm for Max-Clique. Analysis: Suppose the maximum clique in G has size k. If k < n/log(n), then the algorithm returns a clique of size at least 1, which is trivially at least k log(n)/n. Suppose now that k >=n/log(n). Since there are t=n/log(n) Vis, one of the Vi s must contain a clique of size at least k/t = k log(n)/n, as required.
Questions? Comments?
