CMSC 451 Local Search Randomized Algorithms Slides By Carl Kingsford Department of Computer Science University of Maryland College Park Based on 12 1 12 2 13 2 of Algorithm Design by Kleinberg Tardos Local Search What if we have a hard problem but we can t find an approximation algorithm for it Local search is a general class of algorithms that is often useful in practice Unfortunately we can almost never prove that they will return a good solution Optimization Problems Optimization problems A set C of possible solutions A cost cost c for each c C We re looking for a minimum maximal cost c C Better Energy Landscapes Energy landscapes Gradient Descent Better Take a series of steps improving the solution a little bit each time No guarantee you ll end up at the best solution A Little More Formal Local Search A set of feasible solutions C A neighbor relation between some of these solutions S S 0 for some pairs S S 0 C N S S 0 S S 0 the neighbors of solution S Local Search Local Search Algorithm Schema 1 Define a set of feasible solutions C 2 Define a neighbor relation on these sets 3 Let S0 be some feasible solution 4 Let S S0 5 Repeatedly choose some S 0 N S and let S S 0 Example Vertex Cover Vertex Cover Find the minimum size vertex cover for graph G Define a state S as a set of vertices that is a vertex cover Two states are neighbors if they differ by adding or deleting a vertex Algorithm While there is a neighbor S 0 of S with lower cost let the new S be the lowest cost neighbor Gradient Descent Vertex Cover Empty Graph Gradient Descent Vertex Cover Empty Graph Gradient Descent Vertex Cover Empty Graph Gradient Descent Vertex Cover Empty Graph Gradient Descent Vertex Cover 2 Gradient Descent Vertex Cover 2 If the center node is removed then we have to stop Metropolis Algorithm Physical systems also typically have an energy The Gibbs Boltzmann function says the probability of a system of being in a state of energy E is e E kT where T 0 is the temperature of the system Gibbs Boltzmann 1 0 75 0 5 0 25 0 0 5 1 1 5 2 2 5 3 3 5 4 4 5 5 Metropolis Algorithm 2 Metropolis Algorithm S an initial solution While not done Choose S N S If cost S cost S Set S S Else Delta cost S cost S With probability exp delta kT Let S S EndIf EndWhile Simulated Annealing High values of T means you jump around a lot Low values of T mean you never increase the cost Simulated Annealing Idea Start with high T and reduce it as time progresses Some cooling schedule determines how to change T Lot of work into finding cooling schedules that work in practice Simulated Annealing 2 Simulated annealing used all the time in practice No guarantees but often gets good solutions Often does not too though Randomized Algorithms Randomized Algorithms Randomized Algorithms Allow our algorithms to flip some random coins to make their choices May require that the optimum solution is found with expected good runtime Or may require that we always run in polynomial time and we find the optimum solution with high probability Often run in expectation faster than Quicksort You ve probably seen probablistic algorithms of the first type quicksort When the list of numbers is already sorted a naive deterministic algorithm performs very bad O n2 A solution to this randomly permute the input numbers Then the chance that you are in a bad case is small Global Minimum Cut Global Minimum Cut Given an undirected graph G find a partition of the nodes of G into two non empty sets A and B such that the number of edges that have 1 endpoint in A and 1 endpoint in B is minimized Like minimum cut but in an undirected graph and we don t specify s and t Using Network Flow Let s be some node in G In the global minimum cut s must be separated from something Try all n 1 choices for that something as t and use network flow to compute the minimum s t cut Replace each undirected edge by two anti parallel directed edges Cost is n 1 network flow computations Contraction u w v Contraction step choose a edge and merge its endpoints Contraction Algorithm Contraction Algorithm While G contains more than 2 nodes Choose an edge e uniformly at random Contract e replacing its endpoints with a new node w Each new node is really a supernode that contains a number of original nodes Once we have a graph with only 2 supernodes the supernodes define the cut Proving Correctness Let F be a global minimum cut Suppose F k Every node in G must have degree k Why Therefore E 12 kn The chance that we contract an edge in F in the first step is at most k 2 1 n 2 kn After j contractions After j contractions there are n j supernodes Each super node has degree k Why There are at least 12 k n j edges and the probability that we choose one from F to contract is k 1 2 k n j 2 n j Proof cont The contraction algorithm stops after n 2 iterations It will return the global minimum cut if none of the n 2 contractions picked one of the edges in F Def Ei even that an edge of F was not contracted in step i Pr E1 1 n2 2 Pr Ej 1 E1 E2 Ej 1 n j Probability of Success Pr E1 En 2 Unravel Conditional Expectations Theorem The probability that the contraction algorithm returns the minimum cut is 1 n2 Pr E1 En 2 Pr E1 Pr E2 E1 Pr Ej 1 E1 Ej 2 2 2 2 1 1 1 1 n n 1 n j 3 n 2 n 3 1 n n 1 3 1 2 n n n 1 2 Repeating the contraction algorithm Repeat the algorithm n 2 ln n times The probability that we fail to find the global minimum cut every time is n ln n 2 1 1 1 n n 2 Summary Local Search often simple and works well in practice despite it being hard to prove anything about Randomization often yields simpler faster algorithms Class Summary Basic Graph Algorithms BFS DFS TreeGrowing testing bipartiteness topological sort stable marriage Greedy Methods exchange argument stays ahead argument interval scheduling minimizing lateness optimal caching shortest path MST interval partitioning Divide and Conquer counting inversions closest pair of points integer multiplication Dynamic Programming Weighted interval scheduling memoization subset sum knapsack RNA folding sequence alignment shortest paths Network Flow Ford Fulkerson Max flow Min cut Image segmentation edge disjoint paths circulation with demands bipartite matching linear programming NP completeness NP 3 SAT Vertex Cover Independent Set Graph Coloring 3 dimensional matching Set Cover Hamiltonian Cycle TSP Subset Sum co NP Other Approximation algorithms vertex cover TSP …