Georgia Institute Of Technology

• CSE 6140

• CSE6140 - FINAL - FALL 2015 Instructions: PLEASE WRITE YOUR NAME and GT ACCOUNT ON EACH PAGE. ASK FOR EXTRA PAGES IF YOU NEED THEM. This is an in-class, closed-book exam. No cheat sheet is permitted. No collaboration is permitted. Calculators are permitted. You have 2 hours and 50 minutes to complete this exam. The exam has 6 questions with 7+8+10+10+10+8 = 53 points in total. Recommendation: Start by reading all the questions, and do them in the order in which you find them easiest for you. Keep track of time. Recommendation: Write as neatly as you can. Recommendation: Write partial solutions, and your reasoning as you may get partial points. problem type max score pr1 Short/Approx 7 pr2 Short/ILP 8 pr3 DP 10 pr4 NP 10 pr5 Flows 10 pr6 BnB 8 total 53 1 GT USERNAME: NAME: 1 Short Answers (7 pts) (a) (1 pts) Define Relative Error Bound. (b) (2 pts) What is the strategy to prove a (partial or full) Inapproximability result for an optimization problem? Give one example of such a result that we derived in class (no need to re-derive, just state the formal result we showed). 2 GT USERNAME: NAME: (c) (2 pts) Give one advantage of Approximation Algorithms over Branch-and-Bound and one advantage over Local Search. (d) (2 pts) Give one advantage and one disadvantage of using Local Search as opposed to Backtracking. 3 GT USERNAME: NAME: 2 SHORT QUESTIONS (8 pts) (a) (3 pts) In the proofs for Greedy Algorithms, what is the key idea of an exchange argument for showing the Greedy solution is optimal? What two properties do we need to show that hold for the changed solution after we have done each exchange? (b) (2 pts) Argue quickly why and how an approximation solution can be used to derive a lower bound for the branch-and-bound optimization procedure