Christofides’ algorithm. An approximation algorithm (with an approximation ratio bound of 1.5) for the metric TSP
problem. Finds a minimum spanning tree and then a minimum matching
2
among the odd-degree nodes of the tree,
short-circuiting as needed to make a valid tour of the graph. (See Chapter 11.)
Counting sort. Sort integers with a small value range (with at most Q(n) contiguous values) in Q(n) time. Works
by counting occurrences and using the cumulative counts to directly place the numbers in the result, updating the
counts as it goes. (See Chapter 4.)
Do'stlaringiz bilan baham: |