Class Note for CMPSCI 611 at UMass(1)
Class Note for CMPSCI 611 at UMass(1)
Popular in Course
Popular in Department
This 14 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Massachusetts taught by a professor in Fall. Since its upload, it has received 21 views.
Reviews for Class Note for CMPSCI 611 at UMass(1)
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
CMPSCI611 Greedy Algorithms and Matroids Lecture4 Our next algorithmic paradigm is greedy algorithms A greedy algorithm tries to solve an optimization problem by always choosing a next step that is locally optimal This will generally lead to a locally optimal solution but not necessarily to a globally optimal one When the goal of our optimization is to maximize some quantity we call a locally optimal solution maximal and a globally optimal one maximum If we are minimiz ing the quantity we call these minimal and minimum respectively We begin with a minimization problem that can be solved with a greedy algorithm CMPSCI611 Minimum Spanning Trees Lecture 4 Suppose we have a weighted undirected graph G that is connected A spanning tree is a subset of the edges that is connected and is a tree that is it has no cycles Any connected graph has a spanning tree and it may have many of them A minimum spanning tree MST is a spanning tree that has a total weight sum of the weights of its edges that is no greater than that of any other span ning tree There may be more than one MST in case of t1es Note that edge weights are always positive We may sometimes use edge weights of zero but these could if necessary be thought of as just very small positive num bers Kruskal s Algorithm is a greedy solution to the mini mum spanning tree problem 0 Sort the edges by weight cheapest rst 0 Set F to be the empty set 0 For each edge e in order add 6 to F unless this would create a cycle in F 0 Return F We need a way to determine whether an edge 6 creates a cycle in F To do this we keep track of the connected components of F the sets of vertices of G such that two vertices are in the same component iff there is a path from one to the other in F Let 6 1 y where 1 and y are vertices If 1 and y are in the same component adding 6 to F would create a cycle If not adding 6 merges the two connected components The simplest way to merge the components is to scan a table mapping vertices to components moving each ver tex of the smaller component into the larger one We now need to prove that the Kruskal algorithm actually produces an MST First though a warrnup problem to get us used to working with graphs and induction OneQuestion Final Exam for CMPSCI 250 Let F be a forest a acyclic undirected graph with n ver tices k edges and 0 connected components Prove that e n k Proof by induction on e we show that the desired fact is an invariant As it was in the beginning is now and ever shall be Anglican Book of Common Prayer Base Case No edges n components n n 0 Inductive Step Add an edge it merges two connected components into one since if its endpoints were already connected it would create a cycle By induction 0 n 19 before now 0 l n k 1 Conclusion If we ever reach 19 n 1 then c l and we have a tree Correctness of Kruskal Given a forest F let S F be the set of spanning trees that contain all of F s edges As we add edges the following invariant stays true S F contains an MST Base Case Since G is connected an MST exists and it contains F which is 0 Inductive Step We assume that S F has an MST and we add the cheapest available edge called 6 1 y to F We must show that S F U 6 contains an MST We ll show that for any tree T in S F that doesn t in clude 6 there is a tree that does include 6 and has the same or lower total weight Since T is a tree it contains a path between 1 and y the endpoints of 6 Since there was no such path in F the path contains some edge e that is not in F Our cheaper tree is going to be T T e U 6 Since 6 was the cheapest available edge this set has total weight equal or smaller than that of T But how do we know that T is a tree T T 6 U 6 In T e u 1 was part ofa path from 1 to y In T we can still get from u to v by going from u back along the path to 1 over 6 to y and backward on the path to 1 So the only edge in T that is not in T can be successfully bypassed in T so every path in T can be simulated in T and T is connected Why doesn t T have a cycle A cycle would have to con nect 1 to y by another route But in the tree T there was a unique path from 1 to y and we broke it by removing 6 Conclusion At any time in the algorithm if F is not a tree there must be edges in G that join separate con nected components of F These edges must be at least as expensive as any edges in F since otherwise we would have looked at them already and added them to F be cause they join components of F So the algorithm can stop only when F is a tree At that point SF F so F itself must be an MST Timing of Kruskal The timing will depend on both n the number of vertices and k the number of edges Note that k 2 n l for a connected graph and k g 00 for any graph Sorting the list of edges takes 0k log k time Setting up our table of components for each vertex takes 0n time By the simple method we have described updating the table takes one pass over the table or C71 time We will make n 1 such sweeps for 00 total time because we will add an edge to F exactly n 1 times We also might spend up to 0k time checking edges that we don t add to F Thus Tn k 0k log k C71 0712 0k 0k log k 712 In a few lectures we ll see how to reduce this to 0k log k by using a better union nd data structure CMPSCI611 Subset Systems and Matroids Lecture4 When do greedy algorithms work It turns out that we can give an answer to this question for a wide class of optimization problems A subset system is a set E together with a set of subsets of E called I such that I is closed under inclusion This means that ifX g Y and Y E I then X E I The optimization problem for a subset system has as input a positive weight for each element of E Its output is a set X E I such that X has at least as much total weight as any other set in I We call I the independent sets of the subset system because in general I will be de ned so it will include ex actly those sets that don t have a particular kind of de pendence among their elements Let s see some exam ples Examples of Subset Systems Example 0 Let E be any set of vectors in some vector space and let I be the set of sets of linearly independent vectors Clearly this I is closed under inclusion This is the origin of the name independent sets Example 1 E 616263 I 061 2 37 17 27627693 The closure under inclusion can be checked directly I can also be described as all sets that don t contain both 61 and 63 Example 2 Let E be the edges of an undirected graph and I be the set of all acyclic sets of edges Example 3 Let E be the edges of an undirected graph and I be the set of sets of edges that don t have two or edges sharing a vertex These sets of edges are often called independent sets even outside this context and are also known as matchings The Generic Greedy Algorithm Given any nite subset system E I we nd a set in I as follows 0 Set X to 0 0 Sort the elements of E by weight heaviest rst 0 For each element of E in this order add it to X iff the result is in I 0 Return X This certainly gives us a set in I unless I is itself empty since 0 must be in I if any set is It is a maximal set meaning that no element of E can be added to it without bringing X outside of I But a solution to the optimiza tion must be a maximum set with weight greater than or equal to that of any other set in I Our main result is that there is a property of set systems that determines whether this greedy algorithm is guaran teed to give a maximum set for all possible weighting functions 10 Greedy Algorithm Examples Subset System 1 not both 61 and 63 We will get 62 and the larger of 61 and 63 which must be a maximum set in I Subset System 2 acyclic sets This is the Maximum Weight Forest MWF problem which is the same as the MST problem except that a the input graph need not be connected and b we want to maximize instead of minimizing But we can convert the MST problem into an equivalent MWF problem and Vice versa as follows Let m be the maximum weight of any edge in the MWF problem and set the weight of each edge e in the MST problem to be m we E The greedy algorithms produce exactly the same set for the two weighting functions and since the number of edges in the MST must be n 1 a maximum set for one function is a minimum for the other 11 Subset System 3 n0 edges sharing a vertex Here is an example where the greedy algorithm gets a maximal set that is not maximum 3 2 This is Figure 32 of the text The greedy algorithm takes both weight3 edges rst and gets the set in the center with a total weight of 6 But there is a different independent set that has weight 7 shown on the right 12 CMPSCI611 De nition Of a Matroid Lecture 4 A subset system is a matroid if it satis es the exchange property If 239 and zquot are sets in I and 239 has fewer elements than 2 then there exists an element 6 E zquot 239 such that 2 U 6 E I Subset System 1 This is a matroid as we can check the exchange property by inspection For example if 2 61 zquot 62 63 we can let 6 62 Subset System 2 Next lecture we ll show that this is a matroid Subset System 3 This is not a matroid let 239 be the greedy matching and 2quot be the maximum matching in our example There is no edge e at all much less in 2quot that can be added to 239 while keeping it independent 13 Next time we ll prove Theorem For any subset system E I the greedy al gorithm solves the optimization problem for E I if and only if E I is a matroid This is good mathematics We ve found a property of set systems that characterizes the behavior of the greedy al gorithm but doesn t have anything obvious to do with the algorithm Furthermore this property can be expressed in more than one way We ll also prove next time Cardinality Theorem A set system E I is a matroid iff for any set A g E any two maximal independent subsets of A have the same number of elements A property with ostensibly different characterizations is more likely to be mathematically interesting Examples of such properties in CMPSCI 601 include the regular languages and the Turingdecidable languages 14
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'