We recommend downloading and viewing or printing the Postscript files, due
to their much better presentation. Postscript files follow the style of
the text (fonts, sizes, notation, etc.), whereas HTML files use whatever tools
are at hand to render the mathematical formulae.
Exercise 8.10, part 2 (page 346): verify that Maximum Cut remains
NP-complete when restricted to graphs of degree 3.
Retrieve the Postscript file or the
HTML file.
Exercise 8.22 (page 350): verify that approximations within sublinear
distances are NP-hard for the problems discussed so far.
Retrieve the Postscript file or the
HTML file.
Exercise 8.24 (page 350): devise a 1/2 approximation algorithm for
Maximum Cut.
Retrieve the Postscript file or the
HTML file.
Exercise 8.32 (page 352): prove that Maximum Cut is OptNP-complete.
Retrieve the Postscript file or the
HTML file.
