Approximation Algorithms Concepts Approximation algorithm An algorithm that returns near optimal solutions i e is provably good is called an approximation algorithm Performance Ratio Ratio Bound We say that an approximation algorithm for the problem has a ratio bound of n if for any instance of size n the cost C of the solution produced by the approximation algorithm is within a factor of n of the cost C of an optimal solution max I n C C C C n Approximation Algorithm Euclidean TSP Euclidean Traveling Salesman Problem Let C1 C2 Cn be a set of points in the plane corresponding to the location of n cities Find a minimum distance Hamiltonian cycle traveling salesman tour among them An MST based approximation ratio bound 2 Fact cost MST cost Touropt Because 1 SMT is the minimum cost graph that connects all vertices and has only n 1 edges 2 any TSP tour must also connect all vertices and will have n edges Notice that a tour can be viewed as a spanning tree that happens to be a chain plus another edge Approximation Algorithm Euclidean TSP Idea Consider the circuit that consists of a DFS traversal of MST starting from any city and includes an edge in the opposite direction whenever the search backtracks And then we can take shortcut on the tour we get Next slide is an example DFS traversal starting from city a produces a circuit a b c b a d We can then use a shortcut c d to replace original path c b ad Note Being in a metric space Euclidean is just one possibility means that the triangle inequality holds which means that the shortcuts reduce tour cost Approximation Algorithm Euclidean TSP d a b c DSF traversal of MST Taking shortcut from DSF tour e g replacing a b c b a d by a b c d TourHeur 2 MST 2 Touropt Approximation Algorithm Euclidean TSP Complexity of given approximation algorithm The running time is dominated by MST algorithm which in the case of Euclidean graphs is O nlogn Performance Ratio of the given approximation algorithm 2 Approximation Algorithm Euclidean TSP Improving the conversion from the tree traversal into a TSP tour Christofides 1976 New way to look at previous conversion we build an Eulerian circuit on top of the tree by doubling each edge Then we obtain the TSP tour by taking shortcuts from the Eulerian circuit Intuition Tour Heur has less cost than the cost of the Eulerian graph So if we can start with a lower cost Eulerian graph we will get a better bound Try to get a minimum augmentation on the MST such that the resulting graph is an Eulerian graph Approximation Algorithm Euclidean TSP Definition What the Eulerian graph requires every node s degree is even Property of the tree There must be even number of node with odd degree Because the sum of nodes degree in a tree 2 of edges in the tree Approach Add exact one edge for each odd degree node in the MST In particular find a minimum cost matching among the odd degree vertices of the MST and then add an edge between every matched pair The result is an Eulerian graph which we then traverse and shortcut exactly as we did with the doubled MST Approximation Algorithm Euclidean TSP The SMT plus the matching the red line is the Eulerian circuit The tour obtained by taking shortcut from Eulerian circuit Approximation Algorithm Euclidean TSP Consider optimal TSP tour Nodes marked by triangles are odd degree nodes in MST The solid line represents the opt TSP tour The red dashed lines and blue dashed lines represents two possible matching among those odd degree nodes Either total length of blue lines or total length of red lines 0 5 Touropt the minimum matching is no more costly than either the red or blue matching If we use Min Matching the distance of Eulerian graph will be no more than 1 5 Touropt Approximation Algorithm Euclidean TSP Ratio Bound of new approach 3 2 Complexity We have O n 3 min matching algorithm for general graphs Gabow 1976 or Lawler 1976 and O n 2 5 logn 4 algorithm for Euclidean graph Vaidya 1988