The '''multi-fragment (MF) algorithm''' is ana [[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 namealgorithm "multi-fragment"builds comesa fromtour for the facttraveling thatsalesman thisone algorithmedge at a time and thus constructsmaintains ''multiple''intermediatetour partialfragments, tourseach 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 "''fragments''")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 |url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.92.1635&rep=rep1&type=pdf }}</ref>.
