Approximation Algorithms
webpage under construction
Term: Spring 2008
Time: TBA
Location: TBA
Instructor: Pawel Wocjan
Office hours: TBA
Syllabus
Most optimization problems, including those arising in important applications areas, are NP-hard. Therefore, under the widely believed conjecture P<>NP, their exact solution is prohibitively time consuming. But these problems are too important to abandon merely because obtaining an optimal solution is intractable. There are at least three approaches to dealing with NP-hardness. First, if the actual input sizes are small, an algorithm with exponential running time may be perfectly satisfactory. Second, we maybe able to isolate important special cases that are solvable in polynomial time. Third, it may be possible to find near-optimal solutions in polynomial time. In practice, near-optimality is often good enough. An algorithm that returns near-optimal solutions is called an approximation algorithm. This class focuses on the design of efficient approximation algorithms.
A preliminary list of topcic is:
- Intelligent exhaustive search (backtracking, branch-and-bound)
- Local search heuristics (evolution)
- Performance ratios for approximation algorithms
- The approximability hierarchy
- Vertex Cover
- Clustering
- Travelling Salesman Problem
- The general Travelling Salesman Problem
- Knapsack
- The Set-Covering Problem
- Randomization and Linear Programming
- A randomized approximation algorithm for MAX-3-CNF satisfiablity
- Approximating weighted vertex cover using linear programming
- The Subset-Sum Problem
- Semidefinite Programming
- ...
Books:
The required text is
Approximation Algorithms,
by Vijay V. Vazirani, Springer.
Grading Policy:
The final grade will be determined as follows: Homework Assignments 1/3; Midterm Exam 1/3; Final Exam 1/3
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 study groups of two to four people.
However, you are required to turn in the solutions on your own, and you must never copy the solutions of other students.
No late homework and make-up tests will be accepted except for exceptional situations (handeled individually). All exams are closed books, closed notes, and no calculators.
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
Homeworks