Approximation algorithms

Concepts of approximation algorithm , approximation ratio, examples, travelling salesman problem analysis, it's application, pros and cons.

1. Approximation Algorithms Bipesh Subedi ME 2021 , Computer Engineering DoCSE

2. Outline ‹#› Introduction Optimization Problem Statement Approximation Ratio Examples of Approximation algorithms Travelling Salesman Problem (TSP) Analysis Application Pros and Cons ‘Conclusion

3. Introduction Approximation algorithms refers to the efficient algorithms that finds a solution to an optimization problems ( in particular NP-Hard problems ) that is provably close to optimal solution. When it is used ? When finding an optimal solution is very difficult In some cases, where exact solution is not needed and near-optimal solution can be found quickly ‹#›

4. For NP-Complete problems, there is possibly no polynomial-time algorithms to find an optimal solution. The idea of approximation algorithms is to develop polynomial-time algorithms to get near optimal solution. ‹#›

5. Optimization Problem It refers to the problem of finding best option/solution among all feasible/possible solutions. Various important applied problems involve in finding the best possible way to accomplish the task which is often done by finding the maximum or minimum values to a function . Maximization Problem : Finding the maximum optimal value Minimization Problem : Finding the minimal optimum value For example: the minimum time to make a certain journey, the minimum cost for doing a task, the maximum power that can be generated by a device, and so on. ‹#›

6. Statement An algorithm for a problem of size n has an approximation ratio ρ(n) if for any input, the algorithm produces a solution with cost C that satisfies the property: Where Copt is the cost of optimal solution and ρ(n) is a constant or a function of n. ‹#›

7. Approximation Ratio The approximation ratio of an algorithm is the ratio between the result obtained by the algorithm and the optimal cost. Significance Performance Guarantee: It guarantees that the result produced by the approximation algorithm is not going to be worse than a factor of ρ(n) compared to the optimal solution. ‹#›

8. The algorithm with approximation ratio ρ(n) is then called ρ(n)-approximation algorithm . Here we will consider our approximation algorithm to have constant approximation ratio. For example: If ρ(n) = 2 then, For maximization problem : our solution will be no less than half the optimal solution. ( C opt /C <= 2 ) For minimization problem : our solution will be no more than twice the optimal solution. (C/C opt <= 2) ‹#›

9. Range of Approximation ratio If ρ(n) =1 then, The algorithm can always find a optimal solution If ρ(n) >1 then, It gives the approximation in which the algorithm works . ‹#›

10. ‹#› Examples of Approximation algorithms Travelling salesman Problem Vertex-Cover Problem Bin Packing

11. Travelling Salesman Problem (TSP) A salesman should visit all the cities exactly once starting from one city and return back to the starting city such that the total length of the tour should be minimum. It is a NP-Complete problem so, there is no polynomial time. Use an approximation algorithm with a constant approximation ratio. ‹#›

12. Special Case of Travelling Salesman Problem (TSP) Triangle Inequality Property a + b >= c b + c >= a a + c >= b ‹#›

13. Approach ‹#› Step 1: Start with a complete graph. Step 2: Compute a Minimum Spanning Tree (MST) using algorithms like Prim’s, kruskal’s. Step 3: Perform a Depth-First Search (DFS) traversal. Step 4: Delete duplicate vertices. Step 5: Join the edges in the order to obtain approx. tour walk.

14. Given a weighted, undirected graph, start from certain vertex, find a minimum route to visit each vertices once, and return to the original vertex. ‹#›

15. Computing Minimum Spanning Tree Kruskal’s algorithm Steps: 1. Sort all the edges in non-decreasing order of their weight. 2. Pick the smallest edge. Check if it forms a cycle in the spanning tree formed so far. If no cycle is formed, include this edge. Otherwise, discard it. 3. Repeat step 2 until it is a spanning tree. ‹#›

16. After computing the minimum spanning tree , we perform a depth-first search in the MST starting from a vertex A. ‹#›

17. MST-DFS ‹#› A -> B -> D -> B

18. ‹#› A -> B -> D -> B -> E -> B -> A

19. ‹#› A -> B -> D -> B -> E -> B -> A -> C -> A

20. After deleting duplicate vertices we get, A -> B -> D -> E -> C -> A path. Joining the edges in the above order we obtain the approx. tour route. ‹#›

21. Analysis Depth first tree tour (DFTT) length is exactly twice the MST’s weight. MST weight is not more than the length of optimal tour The tour length is at most twice the optimal length i.e C <= 2 x C opt So, in this case ρ(n) = 2 Cost found by the APPROX-MST-DFS algorithm : C = 15 + 10 + 25 + 25 + 30 = 105 Optimal cost ( C opt ) = Sum of MST weights = 15 + 10 + 25 + 10 = 60 C/C opt <= ρ(n) 105/60 <= 2 1.75 <= 2 ‹#›

22. For companies like FedEx and their comp etitors traveling salesman problem is used as a reference to solve related /similar problems. Can be used in network design and routing purposes. Used in astronomy to determine the fastest way of drilling an aluminium disk placed at the focal point of telescope for each spot of interest to collect the light from the galaxy or star over a given period of time . ‹#› Application

23. Pros Deals with NP- Complete problems Finds solutions which are close to optimal solution in polynomial time Cost Effective Cons This technique does not guarantee the best solution May not be useful in all practical application ‹#›

24. Conclusion To conclude we can say that t he goal of an approximation algorithm is to come as close as possible to the optimum value in a reasonable amount of time which is at the most polynomial time. ‹#›

25. Thank you !! ‹#›