# Approximation Algorithm To Solve Computer Science Essay

Published:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Travelling salesman problem is a NP complete problem and can be solved using approximation algorithm. It is a minimization problem starting and finishing at a specified vertex after having visited each other vertex exactly once. Often, the model is a complete graph. An algorithm that returns near-optimal solutions is called approximation algorithms. Through analysing the Metric TSP the performance of approximation algorithm can be improved significantly using graphical analysis of spanning trees and depth first search and implementing a parallel algorithm/program to find a path with approximately minimum travelling cost.

Keywords- TSP, approximation algorithm

Introduction

Travelling salesman problem predicts the shortest possible route to connect different cities based on given distances between each city. Here each city should be traversed only once and finally the person tracing the route should reach to the starting point of the journey with the minimal cost of the whole journey.

Solving a TSP requires application of many graph algorithms which are helpful in analysing the TSP and hence the in finding the optimal solution of TSP.

We call the solution optimal because TSP is a NP hard problem it means TSP cannot be solved in polynomial time that is, it is at least hard as hardest problem in NP. TSP is a challenge to the field of algorithms, many researches are going on to find the solution for TSP and hence for the set of NP hard problems.

But optimal solutions can be found using algorithms such as

Exponential Time Algorithm

Pseudo Polynomial Time Algorithm

Approximation algorithm

There is a third approach; Approximation algorithms are useful in finding near optimal solutions which are helpful in predictions, decision problems, operational research, and search problems. These approximation algorithms have the output which do not deviate much with the optimal solution for the given problem and solves the purpose. Approximation algorithms are provably fast and run in polynomial time and provide us with a solution somewhat close to the optimal solution.

Approximation algorithms are used for maximisation or minimization based on the problem. When it comes to Travelling Salesman Problem, it is a minimization problem as the task is to minimize the total cost of a round trip starting and finishing at a specified vertex after having visited each other vertex exactly once. Often, the model is a complete graph (i.e. each pair of vertices is connected by an edge). If no path exists between two cities, adding an arbitrarily long edge will complete the graph without affecting the optimal tour.

In the symmetric TSP, the distance between two cities is the same in each opposite direction, forming an undirected graph. This symmetry halves the number of possible solutions while in the asymmetric TSP, paths may not exist in both directions or the distances might be different, forming a directed graph.

For the problem of input size 'n' the approximation ratio ρ(n) is defined the maximum of the ratio of the approximate solution to that of the optimal solution and optimal solution to the approximation .That is,

Hence the algorithms with the approximation ratio of ρ (n) are called as ρ (n) - Approximation algorithm. Approximation ratio is always greater than 1 also in case of ρ (n) = 1 the algorithms gives the optimal solution.

Metric TSP

Here we consider a special case of Travelling Salesman Problem named Metric TSP which is a NP complete problem. Metric TSP has some constraints,

If graph G denotes the network of the cities where all the vertices represent cities and the edges represent the path between them, First It should not have any self-loop, second there is exactly one path which is bi-directed with minimal edge cost between two vertices, Also if a direct path exists between the two vertices then that path is smallest when compared with any other indirect path that is through other nodes that is vertices should hold triangle inequality constraint.

These constraints can be written in mathematical for as,

Graph G specified as an n x n Matrix D in which D [i, j] denotes the distance between the vertices I and j such that D forms a metric, i.e.

For all i D[i,i]=0

For all i.j D[i,j]=D[j,i]

For all i,j,k D[i,j] <= D[i,k] + D[k,j]

Output of the approximation algorithm will be a cycle in the graph passing through all vertices exactly once such that the sum of distances associated with the edges in the cycle is as small as possible.

Advantage of using approximation algorithm for TSP

Approximation algorithms are useful in approximation of optimal traversal for a given set of cities or nodes. When the accurate results are not necessary means you don't need to have the exact solution but an approximation or a solution near to the optimal solution is sufficient and the time matters. As stated above in this TSP is an NP -Hard problem which do not have any algorithm which can find the optimal solution in polynomial time. Approximation algorithms provide with a near optimal solution with in polynomial time.

V. Related works and Existing Solution

Metric TSP is NP-complete hence there exists a 2-approximation algorithm for to approximate the solution with the approximation ratio ρ(n) of 2where n is the number of cities to traverse. For this approximation algorithm, the weight of a minimum weight L spanning tree T of G (with D the weight matrix) is a lower bound on the length of an optimal tour on G which is proved if any edge is removed from that spanning tree the graph gets disconnected. Hence the cost of the path is at least equal to the weight of spanning tree.

The upper bound is the length of depth first search of the spanning tree with the minimal weight. That is twice the weight of the spanning tree equal to 2L.Hence the optimal solution C lies in {L, 2L}.

L < C ≤ 2L

Existing serial 2-Approximation Algorithm

Find T = MST of G for weight matrix D. Weight(T) = L

Find E = Sequence of vertices visited in DFS of T

V appears more than once in E, Delete first appearance.

Repeat the previous step while possible.

Return E.

There is not a specific algorithms specified to use for the generation of spanning while solving TSP also the serial depth first search having high complexity of O(|V|+|E|) .Over all the 2-approximation algorithm for the metric TSP problem is a feasible and operates very quickly still the existing serial algorithms is not as fast as it should be while executed on the multicore system environment because it cannot utilize the CPU's or threads available freely for computation and hence over loading a single core or processing unit which is a disadvantages of existing solution.

Proposed solution

When it comes to speed and time complexity the above serial algorithm takes more time to execute and not a feasible solution to the problem for getting approximation for metric TSP. This paper improve the 2-approimation algorithm and proposes a new algorithm for metric TSP which is again a 2-approimation but it takes lesser time to execute and to get a solution for minimization problem of Metric TSP.

This algorithms generates the spanning tree using Prim's algorithms which has time complexity of O ( E + V log V ), usefulness of Prims algorithms comes when there are more number of edges in to the graph ,it performs faster. After getting the spanning tree, the tree is traversed using depth first traversal in which use of parallelism and recursion provides with an efficient algorithm for the Metric TSP also the complexity of the algorithm depends on the number of processor or core executing the algorithm.

Parallel 2-approximation algorithm for metric TSP

Parallel algorithm for the 2-approximation algorithm of metric TSP

Graph G denotes the network of cities to traverse

D is the Adjacency cost matrix of G

C array of vertices traversed as the solution

Algorithm:

sol_tsp (graph G with matrix D)

Generate spanning tree T for the Graph G with the root node a.

C [0] = a;

Call p_approx_tsp (a);

Store the return of the function call in C array starting from C [1].

Return C and cost of traversal.

//p_approx_tsp function used above will be

p_approx_tsp (p)

Z: 2-d array where Z[α] denotes the return of the function call p_approx_tsp (α)

i=0;

//Execute for in parallel or assign the call p_approx_tsp (α) to work pool to be executed by the threads running in parallel.

For all nodes α connected to p

call p_approx_tsp (α)

store return in Z[α]

increment i by 1;

//each p_approx_tsp call is independent hence can be executed in parallel

y: array of nodes as solution by the function

k=0;

for j = 0 . . . i

h=0;

while Z[j] not empty

y[k] = Z[j] [h];

increment k by 1;

end for

y[k] =a;

return y;

Experimental works and flow of algorithm

The above parallel algorithm for the approximation of metric TSP provides us with the solution with the approximation ratio ρ of 2 but the time to find the solution is reduced significantly.

The load is balanced on the processors which improves the performance of the code and reduces the overhead of complex calculations on a single processor. A small set of cities is traced for the solution for understanding the flow of parallel algorithm.

Step 1:

With the root node A when the algorithm further proceeds we found the approximate solution for the metric TSP problem in a parallel and recursive manner.

Hence we get the solution as,

A G F D E C B A and the cost will be 53

Step 2:

This will be the approximately optimal solution,

Further for the larger problem size the algorithm is scalable as well as for multicore processors with n number of cores and hence can be a improvisation of 2-approximation.

Results and conclusion

Hence the parallel 2-approximation algorithm will provide us with a near optimal solution with an significant reduction in the time to generate near optimal solution. The use of Prim's algorithm for generation of spanning tree helps to manage the dense graphs and the parallelization and recursive computation of the solution reduces the complexity and hence the performance.

Future work

Future works include the improvisation in the complexity of this algorithm. There exist 4/3 approximation and 1.5 approximation algorithms for metric TSP which are highly complex hence using parallelization for those algorithms may help in reducing their complexity , and execution time. Optimization of general TSP without constraints and further more applications of TSP, parallel algorithms and graph theory will be areas of research.