1. Refer to the algorithm for the TSP problem in our textbook which yields a TSP cycle which is 2 times the size of the smallest TSP cycle. Recall his algorithm works when the graph satisfies the triangle inequality.
i. Give an example of a complete graph F which satisfies the triangle inequality and where this approximation is more than 1.5 times the size of the optimal (smallest) TSP cycle in F.
ii. Show the steps of the algorithm (as given on page 1114 Theorem 35.2) on your graph F and
state which MSWT your algorithm chooses as well as the size of the TSP cycle your algorithm finds.
2. Consider the randomized min-cut algorithm (Karger’s algorithm) which comes from the randomized algorithm notes posted on the home page.
Suppose that we modify our algorithm as follows: At each step of our min-cut algorithm, instead of choosing a random edge for contraction we choose two vertices at random and contract those vertices together (even if there is no edge between them). We still halt after |V |−2 contraction steps
Give an example of a graph where, when we use the modified min-cut algorithm the probability of find a min-cut is exponentially small. (That is the probability should be no more than 1/f(n) where f(n) is some exponential function. ) Give proof of this if you can, or if not, do your best to explain your reaoning.
0 comments