# COT6938 Approximation Algorithms

Term: Fall 2008
Time: M W 1:30—2:45pm
Location: BA2 0221

Instructor: Pawel Wocjan
Office hours: M W 11:00-12:15pm

### Syllabus

Most optimization problems occurring in real-life situations are NP-hard. For this reason, we cannot hope to efficiently determine optimal solutions. However, we cannot simply give up because of the need to solve truly large instances of computationally hard problems, such as those arising from the Internet or the human genome project.

The field of approximation algorithms has developed in response to the difficulty in solving optimization problems exactly. The goal is to design algorithms that efficiently determine approximate solutions to NP-hard problems, together with provable guarantees that these solutions are never too far from the optimal ones. The course introduces the common design principles underlying approximation algorithms and presents efficient solutions for a wide range of optimization problems. These include:

Techniques: Greedy Algorithms, Layering, Parametric Pruning, Linear Programming, Semi-definite Programming

Problems: Vertex cover, Set cover, Steiner Tree, Traveling Salesman Problem, Multiway Cut and k-Cut, k-Center, Feedback Vertex Set, Shortest Superstring, Knapsack, Bin Packing, Minimum Makespan Scheduling, Facility Location, Maximum Satisfiability

The course also provides a brief introduction to other methods for coping with NP-hardness such as “intelligent” exhaustive search (backtracking, branch-and-bound) and local search heuristics (simulated annealing).

Books:
Chapter 9 Coping with NP-completeness of the book Algorithms by S. Dasgupta, C. Papadimitriou, and U. Vazirani. The required text is Approximation Algorithms, by Vijay V. Vazirani.

The final grade will be determined as follows: Homework Assignments 1/2; Final Presentation/Project 1/2

Grades A, B, C, D, and F are based on the straight-percentage scale (that is, 90% or above is A, 80% to 89.99% is B, etc.)

To enhance your learning experience and to help you solve the homework problems, you are encouraged to work in teams of two to three people. Each team can turn in only one set of solutions, but I will ask each team members to explain the solutions, code, etc.

No late homework and make-up tests will be accepted except for exceptional situations (handeled individually).

Please read and understand student rights and responsibilities including conduct rules clearly stated in UCF’s golden rules, at http://www.goldenrule.sdes.ucf.edu/2e_Rules.html

### Lectures

 Topic Covered Matrial Lecture #1 (08/25) Coping with NP-Completeness     Intelligent Exhaustive Search         Backtracking         Branch and Bound     Local Search     Approximation Algorithms Chapter 9 of Algorithms by SCU Lecture #2 (08/27) Local Search     Randomization and Restarts     Simulated Annealing Chapter 9 of Algorithm by SCU Lecture #3 (09/03) Definition of Approximation Algorithms Vertex Cover     Lower Bounding OPT Section 1.1 Lecture #4 (09/08) Set Cover     The Greedy Algorithm     Layering Section 2.1 - 2.2 Wednesday(09/10) No Class Lecture #5 (09/15) Steiner Tree and TSP     Metric Steiner Tree Section 3.1 Wednesday (09/17) No Class Lecture #6 (09/22) Metric TSP Section 3.2 Lecture #7 (09/24) Multiway cut and Minimum K-cut     Multiway Cut     Minimum K-cut Section 4.1 - 4.2 Lecture #8 (09/29) Minimum K-cut Section 4.2 Lecture #9 (10/01) K-Center     Introduction Section 5.1 Lecture #10 (10/06) Parametric Pruning Applied to Metric K-center Section 5.1 Lecture #11 (10/08) Feedback Vertex Set     Cyclomatic Weighted Graphs Section 6.1 Lecture #12 (10/10) Cyclomatic Weighted Graphs Section 6.1 (Make-up session for 09/10 and 09/17) Lecture #13 (10/13) Layering Applied to Feedback Vertex Set Knapsack     Introduction Section 6.2, 8.1 Lecture #14 (10/15) A Pseudo-polynomial Time Algorithm for Knapsack     An FPTAS for Knapsack     Strong NP-hardness and The Existence of FPTAS's Section 8.1 - 8.3 Lecture #15 (10/20) Bin Packing     An Asymptotic PTAS Chapter 9 Lecture #16 (10/22) Minimum Makespan Scheduling     Factor 2 Algorithm     A PTAS for Minimum Makespan         Introduction Section 10.1 Monday (10/27) No Class Lecture #17 (10/29) Bin packing with fixed number of object sizes         Reducing makespan to restricted bin packing Section 10.2.1 - 10.2.2 Lecture #18 (11/03) Introduction to LP-Duality     The LP-duality theorem     Min-max relations and LP-duality Section 12.1 - 12.2 Lecture #19 (11/05) Two fundamental algorithm design techniques         A comparison of the techniques and the notion of integrality gap Set Cover via Dual Fitting     Dual-fitting-based analysis for the greedy set cover algorithm Section 12.3, 13.1 Lecture #20 (11/10) Dual-fitting-based analysis for the greedy set cover algorithm Rounding Applied to Set Cover     A simple rounding algorithm Section 13.1, 14.1 Lecture #21 (11/12) Randomized rounding     Half-integrality of vertex cover Section 14.2 - 14.3 Lecture #22 (11/17) Set Cover via the Primal-Dual Schema     Overview of the schema     Primal-dual schema applied to set cover Section 15.1 - 15.2 Lecture #23 (11/19) Maximum Satisfiability     Dealing with large clauses     Derandomizing via the method of conditional expectation     Dealing with small clauses via LP-rounding Section 16.1 - 16.3 Lecture #24 (11/24) A 3/4 factor algorithm Section 16.4

### Final Presentations/Projects

 Date Student Topic Wednesday 11/26 George Defensive Alliances Monday 12/01 Cuncong Shortest Superstring Wednesday 12/03 Dan, Steven Facility Location Saturday 12/06 Greg Supergraph Saturday 12/06 Chen-Fu Introduction to Fully Polynomial Randomized Approximation Schemes Saturday 12/06 Hamed Introduction to PCP and Hardness of Approximation Saturday 12/06 Raymond Rectilinear Steiner Arborescence ( Demo ) ( Notes ) Saturday 12/06 Michael, Nadeem Rectilinear Zero-Skew Tree Saturday 12/06 Evan, Jon, Swastik Euclidean TSP

Note: The Saturday session is a make-up session for 10/27 .

### Homeworks

• Homework 1 [pdf] out on 08/27, due on Thurs 09/08 before class (extended to 09/24).
• Homework 2 [pdf] out on 09/29, due on Wed 10/13 before class (extended to 10/29).
• Homework 3 [pdf] out on 10/22, due on Wed 11/12 before class (extended to 11/19).