Page 158 - Innovations in Intelligent Machines

150 S. Rathinam and R. Sengupta
that are close to the optimal solution in an efficient way, then the quality of
using an algorithm can be found out by comparing the solution produced by
the algorithm directly with the lower bound than with the optimal solution
which may require a large time to compute. The experimental results in [7]
show that even for large size problems, Held-Karp’s lower bound gets within
1-2% of the optimal solution. An important feature of Held-Karp’s algorithm
is that the results are very close to the optimal solution for any general cost
function (i.e. cost function doesn’t have to satisfy triangle inequality). Hence,
in the context of UAVs, this might be ideal as the cost function could be
determined by the risk of travelling between any two destinations and hence,
may not satisfy triangle inequality.
In this section we review three algorithms, namely the 2-Approx algorithm,
the 1.5-Approx algorithm and the Held-Karp’s lower bounding algorithm that
can be used to address the SVP.

2.3 Algorithms
Before we present the algorithms, we define some of the terms commonly
used in the TSP literature. Let {i, j} indicate the edge joining vertex i and

vertex j. A subgraph G of G is defined as G := (V, E ) where E ⊆ E.The
cost of a subgraph is defined as the sum of the cost of all the edges present in
E . A spanning tree is a subgraph of G that spans all the vertices in V and

does not contain a cycle. A minimum spanning tree of G is a spanning tree
of G that has minimum cost. The degree of a vertex v in graph G =(V, E)
indicates the total number of edges present in E incident on v. An Eulerian
graph is a graph where each vertex has an even degree. A perfect matching

of a graph G corresponds to a subgraph G of G that has each vertex having
a degree equal to 1. An Eulerian walk of G is a path that visits each edge in
G exactly once and each vertex in G atleast once.
2-Approx Algorithm

Assuming the costs are symmetric and satisfy triangle inequality, the approxi-
mation algorithm 2-Approx [2] is as follows:
1. Find the Minimum Spanning Tree (MST) of the graph G. An example
illustrating this step of the algorithm is given in Fig. 2.
2. Double every edge in the MST to get an Eulerian graph (Fig. 3).
3. Find an Eulerian walk on this Eulerian graph (Fig. 4).
4. Find the tour such that the vehicle visits the vertices of G in the order of
their first appearance in the Eulerian walk (Fig. 5).
The following theorem in [2] shows that 2-Approx has an approximation
factor of 2.
Theorem 1. The algorithm 2-Approx solves the SVP with an approximation
2
factor of 2 in O(n ) steps when the costs are symmetric and satisfy triangle
inequality.