Unformatted text preview:

Introduction to Algorithms December 6, 2003Massachusetts Institute of Technology 6.046J/18.410JProfessors Shafi Goldwasser and Silvio Micali Handout 30Problem Set 9This problem set is not to be handed in.Reading: Chapters34,35.Problem 9-1. The challenges of industrial researchWe say that a graph has a spanning graph of degreeif there exists a subset of edgessuch that (1)is a connected graph and (2) the degree of each vertex inis at most. Such ais called a degreespanning graph of. This problem haspractical applications for telecommunications networks where nodes have bounded degrees.You are working as an algorithms designer for a major telecommunications company. A co-workerof yours has been working on developing an efficient algorithm for the following search problem,SEARCH-SG: given a graph and an integer, find a subset of edgessuch that ! is a degreespanning graph of, if one exists.One day this co-worker leaves the company for a start-up, and the management asks you to takeover his project where he has left off. It turns out that all he has been able to do so far is to design amagic box DECISION-SG#"$%'&(that solves the following decision problem: on input a graph)*and an integer, the magic box outputs+ifhas a degreespanning graph, and,otherwise.(a) Assuming that the magic box that your co-worker designed runs in polynomial time,design a polynomial-time algorithm that solves SEARCH-SG. Prove that your algo-rithm is correct and runs in polynomial time.(b) Suppose that the magic box that your co-worker designed has a bug and does notdo anything meaningful at all. But another co-worker has designed a magic box forthe 3-SAT decision problem. Assuming that her magic box runs in polynomial time,prove that there exists a polynomial-time algorithm that solves the smallest degreespanning graph problem.Problem 9-2. Approximating knapsackRecall from practice quiz 2 the problem of picking out, from a large pile of treasure, the best thingsyou can fit in your knapsack. Specifically, the treasure consists of-objects.0/1.3246575857.:9. Object.<;has size=4;and is worth>?;, for each@A+B1CD4575858-. Your backpack has sizeE, that is, can holda number of objects whose total size is at mostE. You want to carry home as much total worth aspossible.You might remember that on practice quiz 2 we asked you to give an efficient algorithm for thisproblem, assuming that the=<;,>F;andEwere integers. It turns out that that method only works wellwhen the values are small integers— recall that the running time of your algorithm was polynomialinE, not in the size of the encoding ofE, which isGIHE, —in general the problem is NP-hard!2Handout 30: Problem Set 9(a) Show that the knapsack problem is NP-hard by a reduction from the SUBSET-SUMproblem in the book.Probably you’re not going to leave all the treasure sitting there just because you can’t easily figureout how to get the absolute best total worth. So let’s look for an approximation algorithm, that is,one guaranteed to get most of the total worth you can hope for.(b) One obvious algorithm to try is a greedy algorithm: sort the objects in decreasingorder of>F;KJB=6;and go through the list taking an object if it still fits. Show that thereare inputs on which this algorithm might give you an arbitrarily small fraction of theoptimal total worth.(c) Let’s try a slight improvement to part (a): run the greedy algorithm, and find out whattotal worth it would give you. Compare this value to the single most valuable objectthat fits in your knapsack. If the single object is better, take only the single object.Otherwise take the greedy solution. Show that this is a 2-approximation algorithm.(Hint: Reason about the fractional solution—i.e. a solution you would get if you wereallowed to split an object—at the time the greedy algorithm first rejects an object.)Problem 9-3. ReductionsSuppose thatLF/andL2are languages such thatL?/M"NL2. For each of the following statements,either prove that it is true, or prove that it is false, or give a convincing justification for why it is anopen question.(a) LetLF/OL2QPSRUT. IfLV/FPST, thenL2WPST.(b) IfL2WPST, thenLV/FPST.(c) LetL2QPSRUT. IfL2is not NP-complete, then neither isL?/.(d) LetLF/OL2QPSRUT. IfL2("NMLV/, then bothLF/andL2are NP-complete.(e) IfLV/andL2are both NP-complete, thenL2W"NWLV/.Problem 9-4. Easy vs. hard cases of the same problemThe directed Hamiltonian path problem is as follows: given a directed graphXYandtwo distinct verticesZ[\]P^, determine whethercontains a path that starts atZ, ends at\, andvisits every vertex of the graph exactly once.(a) Prove that the directed Hamiltonian path problem is NP-complete. (Hint: consider theHamiltonian cycle problem described in the book.)(b) Design a polynomial-time algorithm that solves the directed Hamiltonian path prob-lem for directed acyclic


View Full Document

MIT 6 046J - Problem Set 9

Download Problem Set 9
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Problem Set 9 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Problem Set 9 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?