View source for Multi-fragment algorithm

{{Short description|Travelling salesman problem heuristic}}
{{one source |date=May 2024}}
{{Infobox Algorithm
|class=[[Approximation algorithm]]
|image=
|caption=
|data=[[Graph (data structure)|Graph]]
|time=<math>\Theta(N^2 \log N)</math>
|space=
|optimal=No
|complete=
}}

The '''multi-fragment (MF) algorithm''' is a [[heuristic]] or [[approximation algorithm|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.<ref name="johnson1997">{{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 }}</ref>

==References==
<references />

[[Category:Travelling salesman problem]]
[[Category:Approximation algorithms]]


{{algorithm-stub}}