- Explain how to use a solution to the bipartite matching decision
problem to find a maximum bipartite matching of a graph. Hint: First
use a binary search to find the size of the maximum matching, then use
self-reducibility to find the set of edges that attains this value.
- CLR Exercise 36.4-7 (pg. 946).
- CLR Exercise 36.5-2 (pg. 960).
- Why are those middle nodes needed in the reduction from undirected
HAM to directed HAM? What would happen if they were omitted?
- Argue that, in non-metric TSPs, for every ratio r>1, there is no
algorithm that can efficiently produce a tour within a ratio bound of
r unless P=NP.
Up: Traveling Salesperson (24)
Previous: Thanks!