Instructor

Kirk Pruhs

Email: kirk@cs.pitt.edu
Phone : 412-624-8844 

Announcements

Course Description

 

This will be an intermediate level graduate course on Approximation Algorithms. In general, the area of approximation algorithms deals with finding efficient algorithms for NP-hard problems that have known worst case performance guarantees. For example, the Traveling Salesman Problem (finding the shortest tour visiting all points in some space) is known to be NP-hard, and thus can not be solved efficiently for all inputs unless P=NP. But if the points are in the Euclidean plane, then there is an efficient algorithm to compute a tour that is at most 50% more than optimal for all inputs. We will concentrate on understanding the main ideas, techniques and concepts at the expense of covering all details. We will concentrate on LP-based algorithms, and in particular on primal-dual algorithms.

Course Text

We will  rather closely follow selected portions of the excellent text authored by   Vijay Vazirani. The table of contents can be found on the Amazon page for the text. The preface, table of contents, and first chapter of the text can be found here. For background on linear programming I recommend:

For background on basic algorithmics I suggest:

Course Format

I will present the overwhelming majority of the lectures. Each student will give one lecture at the end of the term on some paper from the area of approximation algorithms. Most lectures will devoted to understanding a particular problem and a particular algorithm. I use the Socratic method, that is, I try to develop the ideas by asking the students leading questions. The grading will be based on daily homework and the final presentation.

Prerequisites

The ideal background would include an introductory algorithms course such as CS 2150 and an introductory course on mathematical/linear programming (many of algorithms covered in the text use techniques normally covered in an introductory linear programming course). However, the official prerequisite is either an introductory algorithms course or an introductory course on linear programming.

Class Time and Location

Tuesdays and Thursdays from 1:00 to 2:15. We will meet room 5313 of the Sennott Square building, not room 6516 as listed in the schedule of classes.

Tentative Schedule

 

  1. Introduction (2 classes).
  2. K-center (1 class)
  3. Shortest Superstring (1 class)
  4. Review of Algebraic, geometric and economic views of duality (2 classes)
  5. Set cover via dual fitting (1 day)
  6. Set cover via rounding (1 day)
  7. Max SAT (1 day)
  8. Scheduling on unrelated machines (1 day)
  9. Set cover via primal dual (1 day)
  10. Multicut in trees (1 day)
  11. Edge Multiway cut (1 day)
  12. Node Multiway cut (1 day)
  13. Multicut in general graphs (1 day)
  14. Sparsest Cut (1 day)
  15. Steiner forest (1 day)
  16. Steiner  network (1 day)
  17. Facilty location (1 day)
  18. k-median (1 day)
  19. Hardness of Approximation (1 day)
  20. Student Presentations (6 days starting November 11)