Page 160 - Innovations in Intelligent Machines

152 S. Rathinam and R. Sengupta

UAV
destination
direction of travel
Fig. 4. Find an Eulerian walk

UAV

destination
direction of travel
Fig. 5. Find a tour from the Eulerian walk

5. Find the tour such that the vehicle visits the vertices of G in the order of
their first appearance in the Eulerian walk (Fig. 9).

The following theorem in [3] shows that SVP has an approximation factor
of 1.5.

Theorem 2. The algorithm 1.5-Approx solves the SVP with an approxima-
tion factor of 1.5 in O(n 2.5 ) steps when the costs are symmetric and satisfy
triangle inequality.

Held-Karp’s Lower Bound

Held and Karp [5] derived a lower bound to SVP by first noting the fact that
every tour is a 1-tree. A 1-tree is a tree on vertices V = {V 2 ,...V n+1 } with two
additional edges incident on vertex V 1 . So if the minimum cost 1-tree on the set
V turns out to be a tour, it also solves the SVP. The basic idea behind the
Held-Karp algorithm is the observation that the optimal solution of a SVP
does not alter by changing the costs of the edges from c ij to c ij + π i + π j ,