Topic  Covered Matrial  
Lecture #1 (08/25) 
Coping with NPCompleteness 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 Kcut Multiway Cut Minimum Kcut 
Section 4.1  4.2 
Lecture #8 (09/29) 
Minimum Kcut 
Section 4.2 
Lecture #9 (10/01) 
KCenter Introduction 
Section 5.1 
Lecture #10 (10/06) 
Parametric Pruning Applied to Metric Kcenter 
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 (Makeup 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 Pseudopolynomial Time Algorithm for Knapsack An FPTAS for Knapsack Strong NPhardness 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 LPDuality The LPduality theorem Minmax relations and LPduality 
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 Dualfittingbased analysis for the greedy set cover algorithm 
Section 12.3, 13.1 
Lecture #20 (11/10) 
Dualfittingbased 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 Halfintegrality of vertex cover 
Section 14.2  14.3 
Lecture #22 (11/17) 
Set Cover via the PrimalDual Schema Overview of the schema Primaldual 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 LProunding 
Section 16.1  16.3 
Lecture #24 (11/24) 
A 3/4 factor algorithm 
Section 16.4 
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  ChenFu  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 ZeroSkew Tree 
Saturday 12/06  Evan, Jon, Swastik  Euclidean TSP 