Multi-fragment algorithm: Difference between revisions
Content deleted Content added
m stub sort |
|||
| Line 16: | Line 16: | ||
==References== |
==References== |
||
<references /> |
<references /> |
||
{{uncategorized|date=November 2018}} |
|||
{{algorithm-stub}} |
{{algorithm-stub}} |
||
[[Category:Travelling salesman problem]] |
|||
[[Category:Approximation algorithms]] |
|||
Revision as of 00:43, 16 November 2018
| 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 algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it. |