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.

Grading Policy:
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

Announcements

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