Conquer Recurrences and Independent Sets in Algorithms
Explore the concepts of recurrences and independent sets in algorithm analysis. Understand how algorithms with recursion induce branching vectors and how to find the maximum independent set in a graph. Discover strategies for solving linear homogeneous recurrences and optimizing running time based on different input measures.
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
MEASURE AND CONQUER Shlomo Waknine
agenda Recurrence equations Independent set Set cover Dominating set Lower bounds
definitions We define a linear homogenous recurrence to be a sequence of the form: ? ? = ? ? ?1 + ? ? ?2 + +? ? ?? where 1 ?? ?. The vector ? = ?1, ,?? is called the branching vector. The polynom ? ? = ?? ?? ?1 ?? ??is called the characteristic polynomial. Thm: ? ? = ? ??where ? is the unique positive real root of ?. ? is called the branching factor.
example Let ? ? = ? ? 1 + ? ? 2 . The branching vector is 1,2 . The characteristic polynomial is ?2 ? 1. The roots are: 1+ 5 ,1 5 2. 2 The branching factor is 1+ 5 2. ? 1+ 5 2 Thus, ? ? = ?
measure and conquer Every algorithm that uses recursion induces branching vector for each branch. The algorithm induces a tree of its execution. Finding the number of leaves is sufficient to find the running time. Solving each branch recurrence and take the maximum gives us upper bound. We used to analyze algorithms based on a natural parameter of the input. Number of vertices in a graph. using a different measure of the input can give better results.
Independent set Given a graph ? = ?,? , a set ? ? is called independent if there is no edge between each pair in ?. Our goal is to find the independent set of maximum size.
singletons Every singleton vertex must be in the maximum independent set. 2 5 5 7 7 3 1 4 6 6
? ? = 1 If ? has only one neighbor ?, then ? belongs to some maximum independent set. 1 2 w v 3
? 2 If ? 2 then we can find the maximum independent set in polynomial time. ? is composed of trees and cycles. 2 1 1 4 4 3 3
Independent set algorithm 1. If ? ? with ?(?) = 0 then: return 1 + ??? ? ? 2. If ? ? with ?(?) = 1 then: return 1 + ??? ? ? ? 3. If (?) 3 then: choose a vertex ? of maximum degree in ? return max(1 + ???(? ?[?]),???(? ? )) 4. If ? 2 then: return maximum independent set of ? using polynomial time algorithm
simple analysis cont. The algorithm has only one branch on step 3. 3. If (?) 3 then: choose a vertex ? of maximum degree in ? Branching on ? means that ? ? 3. return max(1 + ???(? ?[?]),???(? ? )) Removing ? remove 1 from the original problem size. Add ? to the independent set remove at least 4 from the original problem size. v 4 5 2 1 3 4 5
simple analysis cont. ? ? ? ? 1 + ? ? 4 . The characteristic polynomial is ?4 ?3 1. The branching vector is 1,4 . The roots are: 0.82,1.3803,0.22 + 0.91?,0.22 0.91?. Thus the branching factor is ? 1,4 = 1.3803. ? ? = ? 1.3803?. Can we do better?
better analysis v ?? - number of vertices with degree ?. Assign weight ?2 to vertices with degree 2. 2 1 3 Analyze the running time according to the measure: ? ? = ?2?2+ ? 3 4 5 We analyze the running time with respect to ?2= 0.5.
analysis cont. We have only one branching step. Suppose the algorithm branches on a vertex ? of degree ? 3: OUT the decrease of the measure by discarding ?. IN the decrease of the measure by adding ? to the independent set.
intuition IN case v 2 4 1 3 5 4 5 ?2= 4 ?2= 0 ?3= 2 ?3= 0
analysis cont. Removing ? decreases the measure by 1 in both cases. Let ?1, ,?? be the neighbors of ?. If ? ?? = 2 then the measure is decreased by 0.5 in both cases. If ? ?? 3 then we decrease the measure by 1 in case IN. Thus, ?? + ??? 2 + ? ? . Thus, ? ??,??? ? 1,1 + ? ? . If ? ? 4, then ? ??,??? ? 1,5 < 1.3248.
analysis cont. Suppose we branch on ? with ? ? = 3. Each vertex in ? has degree 2 or 3. Removing ? decreases the measure by 1 in both cases. OUT remove ? decreases the weight of its neighbors by 0.5. IN remove the neighbors of ? decreases the measure by 0.5 or 1. Thus, ???,?? 1 + 3 0.5 = 2.5. Thus, ? ???,?? ? 2.5,2.5 < 1.3196. The running time of the algorithm is ? 1.3248?.
set cover ? set of elements (universe). ? collection of (non-empty) subsets of ?. A set cover of ?,? is a subset ? ? which covers ?: ? = ? ? ? Our goal is to find a set cover ? with minimum cardinality. We assume that ? covers ?.
set cover example ?1,?4,?5,?6 is a cover ?4 ?3 ?5 {?3,?4,?5} is a minimum cover ?1 ?2 ?6
set cover lemma 1 ?3 ?5 ?1 ?2 ?4 If there are two distinct sets ? and ? in ?, ? ?, then there is a minimum set cover which does not contain ?. Thus: msc(?)=msc(? {?})
set cover lemma 2 ?4 ?3 ?5 ?1 ?2 If there is an element ? of ? which belongs to a unique ? ?, then ? belongs to every set cover. Thus: msc(?) = 1+msc(del(S,?)) where: del(S,?) = {Z | Z = R\S ?,R ?}
set cover lemma 3 For a given MSC instance ? such that all the subsets ? of ? are of cardinality two, MSC can be solved in polynomial time. Reduction to maximum matching. 2 4 1 ? = 1,2,3,4,5 1,2 , 1,3 , 2,3 , 2,4 , 3,5 , 4,5 ? = 3 5 ??? ? = 1,3 , 2,4 , 4,5 or ??? ? = 1,3 , 2,4 , 3,5
set cover analysis ?3 ?5 ?? - number of subsets ? ? of cardinality ?. ?? - number of elements ? ? with frequency ?. We analyze the running with respect to the following measure: ?1 ?2 ? ? = ????+ ???? ? 1 ? ?4
analysis cont. To simplify the analysis we make the following assumptions: ?? ??+1 ?? ??+1 ?1= ?1= 0 ??= ??= 1 for ? 6. ?? ??+1 for ? 2 ( ?? = ??+1 ??).
analysis cont. Let ? be the number of leaves in the search tree generated by the algorithm to solve a problem of measure ?. Conditions 2 and 3 implies ? ? ?? . Condition 5 implies that ? = 1. Condition 6 implies two subproblems: ????= ? S ???= ??? ?,? ? ? = ????+ ???? ? 1 ?
analyze ???= ??? ?,? Removing ? implies decreasing by ??. ? ? = ? ??? - number of elements of ? of frequency at least ?. Removing ? ? with frequency ? implies decreasing by ??. Overall: ? 2????= ?=2 ? ?3 ?1 5 ????+ ? 6 ?2 ? ? = ????+ ???? ? 1 ?
analyze ???= ??? ?,? Let ? be a set sharing an element ? with ?. ? ? By removing ?, the cardinality of ? is reduced by one. Hence, implies a reduction of the size of ??? by ?? ??. Overall: ?? ? 2 6 ? ?3 ?1 ? 1 ?? ?2 ?? ? 1 ??+ 6 ? 7 ?=2 Hence, ??? ??+ ?=2 + ?? ?=2 5 ????+ ? 6 6 ? 1 ??+ 6 ? 7 ? ? = ????+ ???? ? 1 ?
analyze ????= ? S The overall decrease in the measure is: 6 ?? ??+ ? ???? ??+ ?=2 Where: 0, ?2= 0 ?2= 1 ?2= 2 ?2= 3, ? = 3 ?2 3, ? 4 ?2+ ?2, ? = ?2+ min 2?2,?3 = ?3, ?2+ min 3?2,?2+ ?3 = ?2+ ?3, ?2+ min 3?2,?2+ ?3,?4 = ?4,
analysis end Notice that ??= 0 for ? 7. Hence it is sufficient to restrict ourselves to the recurrences for the cases 3 |?| 7. Need to find optimal (?2,?3,?4,?5,?2,?3,?4,?5). For each combination of the values of ? and ?2, ,??. Which yields branching factor ? < 1.2353. Thus, the overall running time is ? ? = ? 1.2353? + ?.
from set cover to dominating set 2 4 4 ? = 1,2,3,4,5 ? = 1,2,3,4,5 1 ? = ? = 1,2,3 , 2,1,3,4 , 3,1,2,5 , 4,2,5 , 5,3,4 1,2,3 , 2,1,3,4 , 3,1,2,5 , 4,2,5 , 5,3,4 3 3 5
from set cover to dominating set ? is a dominating set of ? if and only if {?[?]| ? ?} is a set cover of {?[?]| ? ?}. ? = ? = ? = ? Thus, we can solve minimum dominating set problem with ? 1.23532?= ? 1.5259?
lower bounds What we did is to find upper bound on the running time of the algorithm. It is useful to find a lower bound. Tells us how good is our analysis.
independent set 1. If ? ? with ?(?) = 0 then: return 1 + ??? ? ? 2. If ? ? with ?(?) = 1 then: return 1 + ??? ? ? ? 3. If (?) 3 then: choose a vertex ? of maximum degree in ? return max(1 + ???(? ?[?]),???(? ? )) 4. If ? 2 then: return maximum independent set of ? using polynomial time algorithm
independent set Define ??= ?,? such that ? = ? and ?,? ? if and only if ? ? = 2. 3 2 1 4 5 6 7
?7 execution 3 2 1 4 5 6 7 Add 3 to the independent set induces subproblem of the form ?? 5. Removing 3 induces subproblem of the form ?? 3. ? ? = ? ? 5 + ? ? 3 . The running time is 1.19386?.
