multi-fragment algorithm

{{Short description|Travelling salesman problem heuristic}}

{{one source |date=May 2024}}

{{Infobox Algorithm

|class=Approximation algorithm

|image=

|caption=

|data=Graph

|time=$\backslash Theta(N^2\; \backslash log\; N)$

|space=

|optimal=No

|complete=

}}

The multi-fragment (MF) algorithm is a heuristic or approximation algorithm for the travelling salesman problem (TSP) (and related problems). This algorithm is also sometimes called the "greedy algorithm" for the TSP.

The algorithm builds a tour for the traveling salesman one edge at a time and thus maintains multiple tour fragments, each of which is a simple path in the complete graph of cities. At each stage, the algorithm selects the edge of minimal cost that either creates a new fragment, extends one of the existing paths or creates a cycle of length equal to the number of cities.{{cite journal |last1=Johnson |first1=David |last2=A. McGeoch |first2=Lyle |title=The Traveling Salesman Problem: A Case Study in Local Optimization |journal=Local Search in Combinatorial Optimization |date=1997 |volume=1 |citeseerx=10.1.1.92.1635 }}