T-79.7001 Postgraduate Course in Theoretical Computer Science (2-10 cr) P V
Spring 2008 (periods III and IV) -- Approximation Algorithms
Many important combinatorial optimisation problems that arise in
diverse application areas such as computer and transportation
networks, manufacturing, and data analysis are NP-hard, and
hence most likely not efficiently solvable by exact algorithms.
Among the many approaches that have been investigated to
circumvent this complexity barrier, the best developed is at
present the methodology of approximation algorithms.
The term refers to efficient optimisation heuristics that,
while not solving the problem exactly, provide some provable
guarantee on the quality of the eventual approximate
solution. Obtaining such a guarantee often requires a profound
understanding of the combinatorial nature of the
problem under study. The methodology of approximation algorithm
design has been developed intensely for the past 20 years, and
it now brings together a powerful and sophisticated collection of models
and techniques from combinatorics and linear programming theory
for the development of such heuristics for a wide variety of
The goal of this graduate seminar is to achieve a working
understanding of the present state of this methodology,
both as a tool for practical algorithm design and as
an active research area, by reading through an in-depth textbook
on the topic chapter by chapter.
The course T-79.7001 replaces the former course
T-79.300 Postgraduate Course in Theoretical Computer Science
- [12 May 2008] The seminar for this Spring is over;
many thanks for your active participation.
The grade sheet for the seminar is available
- [28 Apr 2008] Please provide feedback on the seminar
via the computer science curriculum's
course feedback system. The electronic
questionnaires were opened on Mon 28 Apr and
will close on Tue 20 May.
- [7 Apr 2008] Some further changes to the schedule:
no session on 17 Apr, new sessions on 28 Apr and 5 May,
speakers of the last few sessions permuted.
- [28 Mar 2008] Because of a scheduling conflict,
the session of Mon 31 Mar has been moved forward
by one week, to Mon 7 Apr.
- [22 Jan 2008] Link
added to Crescenzi & Kann's
"compendium of NP optimization problems".
This is a wonderful resource; check it out.
- [22 Jan 2008] Because of a scheduling conflict with
the course T-0.7050 "Introduction to Postgraduate
Studies in Computer Science", the time of the
seminar has been changed from Monday 4:30-7 p.m.
to Thursday 4:30-7 p.m., with a few exceptions.
(See detailed schedule
- [27 Dec 2007] The first seminar session is on Mon 21 Jan.
- Time, place:
Mondays 4:30-7 p.m.
Thursdays 4:30-7 p.m.,
seminar room TB353.
First session Mon 21 Jan.
Prof. Pekka Orponen,
- Registration by
First two years' mathematics courses
including introductory discrete mathematics
(Mat-1.2991), and basic knowledge of the design
and analysis of algorithms (T-106.1220/1223).
Familiarity with advanced algorithmic techniques
(T-79.4201, T-106.4100), computational complexity theory
(T-79.5103), and optimisation theory (Mat-2.2105, Mat-2.3140)
will help in assimilating the material and setting it in
a broader context.
Each full-session seminar presentation plus archivable slides
merits 4 cr. In addition, feedback must be provided for
at least five other speakers using the respective
electronic forms. (Forms available via the seminar schedule
below.) Feedback forms for the presentation in a given week must be
completed by the beginning of the session on the following week.
- The presenter's archivable slides (preferably in PDF)
will be linked to the schedule below by the coordinator.
The seminar will be based on the textbook:
Two copies of the book will be available for short-term loan
and one for reading-room use in the DCSE library.
Seminar talks are in the form of presentations of chapters
from Vazirani's book, according to the schedule below.
- 21 Jan (Monday):
Opening, overview, handing out assigments (P.O.)
- 31 Jan: No seminar.
- 7 Feb:
Basic Problems 1: Set Cover, Steiner Tree, TSP (Chs. 2, 3),
- 14 Feb:
Basic Problems 2: Multiway Cut, k-Cut, k-Center (Chs. 4, 5),
- 21 Feb:
Basic Problems 3: Knapsack, Bin Packing, Scheduling (Chs. 8, 9, 10),
- 25 Feb (Monday!):
Linear Programming and LP Duality (Ch. 12),
- 10 Mar (Monday!):
LP Techniques for Set Cover (Chs. 13, 14, 15),
- 13 Mar:
LP Techniques for Satisfiability and Scheduling (Chs. 16, 17),
- 20 Mar:
Easter break; no seminar.
- 27 Mar:
LP Techniques for Multicuts and Multicommodity Flows (Chs. 18, 20),
31 Mar 7 Apr (Monday!):
LP Techniques for Steiner Forests and Networks (Chs. 22, 23)
Alexey Kirichenko -
Pekka Orponen -
- 10 Apr:
LP Techniques for Facility Location and k-Medians (Chs. 24, 25),
- 17 Apr: No seminar.
17 Apr 24 Apr: Semidefinite Programming (Ch. 26),
- 28 Apr (Monday!):
Hardness of Approximation (Ch. 29),
- 5 May (Monday!):
The Shortest Vector Problem (Ch. 27),
In addition to the seminar text, the following general literature
may be helpful.
- G. Ausiello et al.,
Complexity and Approximation: Combinatorial Optimization
Problems and their Approximability Properties,
- D. S. Hochbaum (Ed.),
Approximation Algorithms for NP-Hard Problems,
PWS Publishing 1997.
- J. Hromkovic,
Algorithmics for Hard Problems: Introduction to Optimization,
Randomization, Approximation, and Heuristics, 2nd Ed.,
Latest update: 12 May 2008.