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.