algorithms
algorithms copied to clipboard
jeffgerickson
[Oops.] Bugs in Approximation Chapter J.9
Please verify that the error is present in the most recent revision before reporting.
Chapter number or note title: J.8
Page number: 11
Error description: typo
Pushing this idea to its limits us the following negative result.
Suggested fix (if any):
Pushing this idea to its limits gives us the following negative result.
Chapter number or note title: J.8
Page number: 12
Error description: typo
Suggested fix (if any):
Swap (3) and (4) in the left graph
Chapter number or note title: J.8
Page number: 12
Error description: bug in proof
On the other hand, if we remove any edge from the optimal tour, we obtain a spanning tree (in fact a spanning path) of the graph; thus, MST ≥ OPT.
Suggested fix (if any):
MST <= OPT.
