15-451 MINI #5: due 11:59pm Nov 29, 2012 Problem 1: Consider the NP-complete 3-SAT problem. Describe a natural "Linear Programming relaxation" of this problem. What are the variables? What are the constraints? (Note: you are not allowed modular arithmetic in Linear Programming.) As with any relaxation, your formulation should have the property that if the original instance was satisfiable, then the linear program you create is feasible (so if the LP is *not* feasible, that is a proof that the original instance was not satisfiable). Problem 2: Why is the above LP relaxation not very useful for determining if a formula is satisfiable assuming that every clause has 2 or more literals in it? (Alternatively, can you describe such a formula where your LP is infeasible?) Problem 3: Consider the following online problem. You are at the GHC elevators and need to go up two floors. Unfortunately, the elevator lights aren't working so you don't know where the elevators are (or even if they are running at all). You press the button and start waiting. How long should you wait until you give up and take the stairs, assuming you care about total time to reach your destination and your goal is to minimize your *competitive ratio*? For this problem, assume walking up the stairs takes 45sec, and that once the elevator arrives, it takes 15sec to get to your floor. For example, the strategy "wait 1 minute, and if it hasn't come by then, give up and take the stairs" would have competitive ratio (60+45)/45 since if the elevator never comes, you will take 60+45sec, whereas had you known that in advance, the optimal thing to do would have been to just take the stairs right away, taking 45sec. We are looking here for a number (in seconds) and reasoning for why that number is correct. You may wish to review the notes from Nov 13.