Instructor
Kirk Pruhs
Email:
kirk@cs.pitt.edu
Phone : 412-624-8844
Announcements
- Student presentations tentatively start on Tuesday
Nov 11.
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
- Introduction (2 classes).
- Approximation algorithms with explicit lower
bound
- Examples: 2-approximate MST algorithm for TSP,
2-approximate matching algorithm for vertex cover, and 2-approximate LP
algorithm for vertex cover
- Reading: Chapters 1 and 3
- Homework: Problem 3.4 and 3.5 from Vazirani. Assume you have a polynomial time algorithm for finding minimum
weight matchings and minimum weight 2-matchings. Due Tuesday Sept. 2
- Approximation algorithms without explicit lower
bounds
- Examples: O(log n) approximate greedy set
cover algorithm and 2-approximate multiway cut algorithm
- Reading: Chapters 2 and 4
- Homework: Problems 2.1 and 2.2. Due Thursday
September 4
- K-center (1 class)
- Reading: Chapter 5
- Homework: Problem 5.3. Due Tuesday September 9
- Shortest Superstring (1 class)
- Reading: Chapter 7
- Homework: Problems 2.16 and 7.2. Due Thursday
September 11
- Review of Algebraic, geometric and economic views of
duality (2 classes)
- Reading: Chapter 12
- Homework: Problems 12.8. Due Tuesday
September 16
- Homework: Problem 12.9. Due Thursday September
18
- Set cover via dual fitting (1 day)
- Reading: Chapter 13
- Homework: Problem 13.6. Due Tuesday September 23
- Set cover via rounding (1 day)
- Reading: Chapter 14
- Homework: Problems 14.3 and 14.5. Due Thursday
September 25
- Max SAT (1 day)
- Read: Chapter 16
- Homework: Problems 16.3, 16.4, and 16.8. In 16.3
and 16.4, can you develop a derandomized algorithm that only needs to
solve 1 LP instance? Due Thursday October 2.
- Scheduling on unrelated machines (1 day)
- Reading: Chapter 17
- Homework: Problem 17.4. Due Tuesday October 7
- Set cover via primal dual (1 day)
- Reading: Chapter 15
- Homework: None
- Multicut in trees (1 day)
- Reading: Chapter 18
- Homework:
18.6. Due Tuesday October 14.
- Edge Multiway cut (1 day)
- Reading: Chapter 19
- Homework: Problems 19.1, 19.2 and 19.3. Due
Thursday October 16
- Node Multiway cut (1 day)
- Reading: Chapter 19
- Homework: Problem 19.9. Due Tuesday October 21
- Multicut in general graphs (1 day)
- Reading: Chapter 20
- Homework: Problems 20.1, 20.3, and 20.15
- Sparsest Cut (1 day)
- Reading: Chapter 21
- No Homework
- Steiner forest (1 day)
- Reading: Chapter 22
- Homework: Problem 22.3. Due Thursday October 30
- Steiner network (1 day)
- Reading: Chapter 23
- Homework: Problem 23.1 Due Tuesday November 4.
- Facilty location (1 day)
- k-median (1 day)
- Hardness of Approximation (1 day)
- Student Presentations (6 days starting November 11)
-
Strategy Proof Mechanisms via Primal-dual
Algorithms. M. Pal and E. Tardos. Talk slides (pdf,
LaTeX)
-
Equitable Cost
Allocations via Primal-Dual-Type Algorithms, K. Jain, V. Vazarani
Talk slides (doc)
-
Market
Equilibrium via a Primal-Dual-Type
Algorithm, Nikhil R. Devanur, Christos H. Papadimitriou,
Amin Saberi, Vijay V. Vazirani. Talk Slides (ppt)
- Multicast Pull Scheduling. Talk Slides (LaTeX,
pdf)
-
Primal-dual algorithms come of age:
Approximating MST's with nonuniform degree bounds,
R.Ravi, J. Köneman. Slides (ppt)
- Minimizing Stall Time. Slides (ppt)