Christofides algorithm (Approximate TSP The Traveling-Salesman Problem)
Jump to navigation
Jump to search
Time Complexity
$O(V^{3})$
Space Complexity
$O(V^{2})$??? words
(Depends on best space complexity for O(V^3) min-weight matching (the rest of the algorithm requires O(V) auxiliary space))
Description
Approximate?
Approximate
Approximation Factor: 1.5
Randomized?
No, deterministic
Model of Computation
Word RAM
Year
1976