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,…,Cnbe 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-a-d. – 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 TSPDSF 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 * Touropta b cdApproximation 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: 2Approximation 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 TSPThe SMT plus the matching: the red line is the Eulerian circuitThe tour obtained by taking shortcut from Eulerian circuitApproximation 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