Multi-fragment algorithm

Multi-fragment algorithm
Class	Approximation algorithm
Data structure	Graph
Worst-case performance
Optimal	No

The multi-fragment (MF) algorithm is an 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 name "multi-fragment" comes from the fact that this algorithm constructs multiple intermediate partial tours (or "fragments") ^[1].

References

^ Johnson, David; A. McGeoch, Lyle (1997). "The Traveling Salesman Problem: A Case Study in Local Optimization". Local Search in Combinatorial Optimization. 1.

This article is a stub. You can help Wikipedia by expanding it.

[johnson1997-1] Johnson, David; A. McGeoch, Lyle (1997). "The Traveling Salesman Problem: A Case Study in Local Optimization". Local Search in Combinatorial Optimization. 1.

[1]