Performance of a simple ACO on the minimum label spanning tree problem

Abstract

Abstract The minimum label spanning tree problem is an NP-complete combinatorial optimization problem. Experiments have shown that the ant colony optimization is effective for solving this problem. However, we theoretically know little about the performance of the ant colony optimization on the minimum label spanning tree problem, which may be due to the randomness and population features of the ant colony optimization. This paper theoretically analyzes the performance of a simple ant colony optimization, called the 1-ANT MMAS* on the problem. We show that the 1-ANT MMAS* is capable to obtain some approximate optimal solution of the minimum label spanning tree problem in polynomial time in average. In addition, we show that the 1-ANT MMAS* is superior to a local search algorithm called ERA on a constructed instance of the problem.

Keywords

• Ant colony optimization
• Computational complexity
• Approximation ratio
• Spanning tree problem
• Minimum label