Applications of Backward Analysis in Minimum Spanning Tree Algorithms
Exploring various algorithms for Minimum Spanning Trees, including Prim's, Kruskal's, and Boruvka's algorithms. Discussing the use of deterministic and randomized algorithms, MST verification, and the Karger-Klein-Tarjan algorithm. Highlighting the concept of light edges in relation to MSTs and the efficiency of solution verification algorithms through backward analysis.
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
Randomized Algorithms CS648 Lecture 17 Miscellaneous applications of Backward analysis 1
Minimum spanning tree 16 d 17 9 v x 4 2 5 h 19 6 11 y 3 3 22 c 12 a 18 15 1 10 u b 7 13 3
Minimum spanning tree 16 d 17 9 v x 4 2 5 h 19 6 11 y 3 3 22 c 12 a 18 15 1 10 u b 7 13 Algorithms: Prim salgorithm Kruskal s algorithm Boruvka s algorithm Less known but it is the first algorithm for MST 4
Minimum spanning tree ? = (?,?) : undirected graph with weights on edges ? = |?|, ? = |?|. Deterministic algorithms: Prim s algorithm 1. O((? + ?) log?) using Binary heap 2. O(? + ?log?) using Fibonacci heap Best deterministic algorithm: O(? + ???? ?) bound Too complicated to design and analyze Fails to beat Prim s algorithm using Binary heap 5
Minimum spanning tree When finding an efficient solution of a problem appears hard, one should strive to design an efficient verification algorithm. MST verification algorithm: [King, 1990] Given a graph ? = (?,?) and a spanning tree ?, it takes O(? + ?) time to determine if ? is MST of ?. Interestingly, no deterministic algorithm for MST could use this algorithm to achieve O(? + ?) time. 6
Minimum spanning tree ? = (?,?) : undirected graph with weights on edges ? = |?|, ? = |?|. Randomized algorithm: Karger-Klein-Tarjan s algorithm [1995] 1. Las Vegas algorithm 2. O(? + ?) expected time This algorithm uses Random sampling MST verification algorithm Boruvka s algorithm Elementary data structure 7
Minimum spanning tree ? = (?,?) : undirected graph with weights on edges ? = |?|, ? = |?|. Randomized algorithm: Karger-Klein-Tarjan s algorithm [1994] 1. Las Vegas algorithm 2. O(? + ?) expected time How close is MST of a random sample of edges to MST of original graph ? Random sampling : The notion of closeness is formalized in the following slide. 8
Light Edge 16 d 17 9 v x 4 2 5 h 19 6 31 11 y 3 3 22 c 12 a 18 15 1 10 u b 7 13 Definition: Let ? ?. An edge ? ?\? is said to be light with respect to ? if MST({?} ?) MST(?) Question: If ? ?? and |?|=?, how many edges from ?\? are light with respect to ? on expectation ? Answer: ?? ?(? ?) <? 9
USING BACKWARD ANALYSIS FOR MISCELLANEOUS APPLICATIONS 10
PROBLEM 1 SMALLEST ENCLOSING CIRCLE 11
Smallest Enclosing Circle Question: Suppose we sample ? points randomly uniformly from a set of ? points, what is the expected number of points that remain outside the smallest circle enclosing the sample? For ?=? ?, the answer is < ?? 13
PROBLEM 2 SMALLEST LENGTH INTERVAL 14
Sampling points from a unit interval Question: Suppose we select ? points from interval [0,1], what is expected length of the smallest sub-interval ? for? = 1, it is ?? for? = 2, it is ?? ? ? ? ? + ?? ? ? General solution : ?? 1 0 This bound can be derived using two methods. One method is based on establishing a relationship between uniform distribution and exponential distribution. Second method (for nearly same asymptotic bound) using Backward analysis.
PROBLEM 3 MINIMUM SPANNING TREE 16
Light Edge 16 d 17 9 v x 4 2 5 h 19 6 31 11 y 3 3 22 c 12 a 18 15 1 10 u b 7 13 Definition: Let ? ?. An edge ? ?\? is said to be light with respect to ? if MST({?} ?) MST(?) Question: If ? ?? and |?|=?, how many edges from ?\? are light with respect to ? on expectation ? 17
USING BACKWARD ANALYSIS FOR THE 3 PROBLEMS : A GENERAL FRAMEWORK 18
A General framework Let ? be the desired random variable in any of these problems/random experiment. Step 1: Define an event? related to the random variable ?. Step 2: Calculate probability of event ? using standard method based on definition. (This establishes a relationship between ) Step 3: Express the underlying random experiment as a Randomized incremental construction and calculate the probability of the event ? using Backward analysis. Step 4: Equate the expressions from Steps1 and 2 to calculate E[?]. 19
PROBLEM 3 MINIMUM SPANNING TREE 20
A BETTER UNDERSTANDING OF LIGHT EDGES 21
Minimum spanning tree 16 d 17 19 (?,?) v x 4 2 5 h 19 6 31 11 y 3 3 22 c 42 a 18 15 1 10 u b 7 13 Random sampling 16 d (?,?) v x 4 5 h 19 31 11 y 22 c a 18 15 1 10 u b 22
Minimum spanning tree 16 d 17 19 (?,?) v x 4 2 5 h 19 6 31 11 y 3 3 22 c 42 a 18 15 1 10 u b 7 13 16 MST(?) d (?,?) v x 4 5 h 19 31 11 y 22 c a 18 15 1 10 u b 23
Minimum spanning tree 16 d 17 19 (?,?) v x 4 2 5 h 19 6 31 11 y 3 3 22 c 42 a 18 15 1 10 u b 7 23 16 MST(?) d 17 19 (?,?) v x 4 2 5 h ?\? 19 6 11 y 3 3 c 42 a 15 1 10 u b 7 23 24
Minimum spanning tree 16 d 17 19 (?,?) v x 4 2 5 h 19 6 31 11 y 3 3 22 c 42 a 18 15 1 10 u b 7 23 16 MST(?) d 17 19 (?,?) v x 4 2 5 h ?\? 19 6 11 y 3 3 c 42 a Light 15 1 10 u b 7 23 25
First useful insight Lemma1: An edge ? is light with respect to ? ?if and only if ?belongs to MST( ? ?). 26
Minimum spanning tree 16 d 17 19 (?,?) v x 4 2 5 h 19 6 31 11 y 3 3 22 c 42 a 18 15 1 10 u b 7 23 16 MST(?) d 17 19 (?,?) v x 4 2 5 h ?\? 19 6 11 y 3 3 c 42 a heavy Light 15 1 10 u b 7 23 27
Minimum spanning tree d (?,?) v x 4 2 5 h 6 MST(?) y 3 3 c a 1 u b 7 Is there any relationship among MST(?), MST(?) and Light edges from ?\? ? 16 MST(?) d 17 19 (?,?) v x 4 2 5 h ?\? 19 6 11 y 3 3 c 42 a heavy Light 15 1 10 u b 7 23 28
Second useful insight Lemma2: Let ? ?and ? be the set of all edges from ?\? that are light with respect to ?. Then MST(?)= MST(? ???(?)) This lemma is used in the design of randomized algorithm for MST as follows (just a sketch): Compute MST of a sample of ?/? edges (recursively). Let it be T . There will be expected ? edges light edges among all unsampled edges. Recursively compute MST of ? T edges which are less than 2? on expectation. 29
Light Edge 16 d 17 9 v x 4 2 5 h 19 6 31 11 y 3 3 22 c 12 a 18 15 1 10 u b 7 13 Definition: Let ? ?. An edge ? ?\? is said to be light with respect to ? if MST({?} ?) MST(?) Question: If ? ?? and |?|=?, how many edges from ?\? are light with respect to ? on expectation ? We shall answer the above question using the Generic framework. But before that, we need to get a better understanding of the corresponding random variable. 30
? ? MST(?) ?\? 31
? ? MST(?) ?\? Light 32
? ? MST(?) ?\? Light heavy 33
?: random variable for the number of light edges in ?\? when ?is a random sample of ? edges. ?: set of all subsets of ?of size ?. . ? ?: number of light edges in ?\? when ? = ?. . ? Can you express ?[?]in terms of ? ? and ? only ? ?[?] = ?? = ?? |?| ? ? ? ? 34
Step 1 Question: Let ? be a uniformly random sample of ? edges from ?. What is the prob. ? that an edge selected randomly from ?\? is a light edge ? Two methods to find ? 35
Step 2 Calculating? using definition 36
Step 2 Calculating? using definition ? ? Light edges =? ? MST(?) ?\? Light heavy 37
Step 2 Calculating? using definition ?: set of all subsets of ?of size ?. . The probability ?is equal to ? ? ? ? ? = ? |?| ? ? ? ? ? = |?| ? ? ? ? ? ? ? = ? ??[?] 38
Step 3 Expressing the entire experiment as Randomized Incremental Construction A slight difficulty in this process is the following: The underlying experiment talks about random sample from a set. But RIC involves analyzing a random permutation of a set of elements. Question: What is relation between random sample from a set and a random permutation of the set ? Spend some time on this question before proceeding further. 39
random sample and random permutation Random permutation of ? ?\? ? ? ? ? Observation: ? is indeed a uniformly random sample of ? 40
Step 3 The underlying random experiment as Randomized Incremental Construction: Permute the edges randomly uniformly. Find the probability that ?th edge is light relative to the first ? ? edges. Question: Can you now calculate probability ? ? Spend some time on this question before proceeding further. 41
Step 3 Random permutation of ? ?? ???? ?? ? 42
Step 3 Random permutation of ? ?? ???? ?? ? ?\?? ? ??: a random variable taking value 1 if ??is a light edge with respect to MST(?? ?). 43
Step 3 Random permutation of ? ?? ???? ?? ? ?\?? ? ??: a random variable taking value 1 if ??is a light edge with respect to MST(?? ?). Question: What is relation between ? and ?? s? Answer: ?? ? = ?(??+?= ?). 44
Calculating ?(??= ?). Random permutation of ? ?? ???? ?? ? Forward analysis ?? ?: set of all subsets of ?of size ? ?. ?(??= ?) = ? ?? ? ?(??= ? ?? ?= ? ?(?? ?= ?) depends upon ? MST(?) 45
Calculating ?(??= ?). Random permutation of ? ?? ???? ?? Backward analysis ??: set of all subsets of ?of size ?. ?(??= ?)= ? ?? ? ?(??= ? ??= ? ?(??= ?) 46
?(??= ? ??= ? Random permutation of ? ?? ???? ?? Backward analysis Use Lemma 2. ?(??= ? ??= ? = ?? = ?? ? 1 ? ? ?th edge ??????? to MST(?) |MST(?)| ? MST(?) 47
Calculating ?(??= ?) Random permutation of ? ?? ???? ?? Backward analysis ??: set of all subsets of ?of size ?. ?(??= ?)= ? ?? ? ?(??= ? ??= ? ?(??= ?) ? 1 ? =? 1 ? ? ?? ? ?(??= ?) =? 1 ? ? ?? ? ?(??= ?) 48
Combining the two methods for calculating ? Using method 1: ? ? = ? ??[?] Using method 2: ? =?(??+?= ?) <? 1 ? + ? Hence: ?[?]<? 1 ? ?+?(? ?) ?(? ?) 49
Theorem: If we sample ?edges uniformly randomly from an undirected graph on ? vertices and ? edges, the number of light edges among the unsampled edges will be less than ? on expectation. ?(? ?) 50
