You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Christofides algorithm is O(n^3) because this is the time it takes to calculate minimum weight perfect matching. So people using your library might assume that this it's time complexity when in fact it's O(n!) (more precisely A000984). Might be a good idea to inform people about it.
The text was updated successfully, but these errors were encountered:
Yeah, basically this whole package does not make any sense, because I can just use brute force and solve TSP with few lines of code with the same complexity.
Agree. This line starts to break the time complexity: bipartite_set = [set(i) for i in itertools.combinations(set(odd_vertices), int(len(odd_vertices)/2))]
Christofides algorithm is O(n^3) because this is the time it takes to calculate minimum weight perfect matching. So people using your library might assume that this it's time complexity when in fact it's O(n!) (more precisely A000984). Might be a good idea to inform people about it.
The text was updated successfully, but these errors were encountered: