Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[Oops.] Bugs in Approximation Chapter J.9 #302

Open
reteps opened this issue Nov 19, 2024 · 0 comments
Open

[Oops.] Bugs in Approximation Chapter J.9 #302

reteps opened this issue Nov 19, 2024 · 0 comments

Comments

@reteps
Copy link

reteps commented Nov 19, 2024

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

image

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant