Multi-fragment algorithm

Multi-fragment algorithm

Class	Approximation algorithm
Data structure	Graph
Worst-case performance	$\Theta (N^{2}\log N)$
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") .