Multi-fragment algorithm: Difference between revisions

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 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..