Worst Case Analysis of Nearest Neighbour Algorithms for the Minimum Weighted Directed $k$-Cycle Problem

Piyashat Sripratak

Abstract

Given a weighted complete directed graph on $n$ nodes, the asymmetric traveling salesman problem (ATSP) is to find a minimum weighted directed cycle of length $n$. This is a well-studied NP-hard problem. Sometimes, we require a cycle containing a specific number of nodes. Thus, we concentrate on finding a minimum weighted directed cycle of length $k$ when $k$ is a positive integer in $\{2,3,\ldots,n\}$. The problem is called the minimum weighted directed $k$-cycle problem (MWD$k$CP), a generalization of ATSP. Nearest neighbour algorithm (NN) and repetitive nearest neighbour algorithm (RNN) for ATSP are known for good computational results on Euclidean ATSP, but poor performances on some graphs. We give instances to show that establishing an approximation ratio for NN is impossible, and a result from NN can be worse than average. We also prove that NN can output a unique maximum weighted directed $k$-cycle, and offer a sufficient condition to avoid that scenario. As for RNN, when $n\neq k$, it has no approximation ratio and can be worse than average. When $n\geq4$, we obtain a lower bound and an upper bound for the domination number of RNN.