
T79.7001 Postgraduate Course in Theoretical Computer Science (210 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 NPhard, 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
applications.
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 indepth textbook
on the topic chapter by chapter.
The course T79.7001 replaces the former course
T79.300 Postgraduate Course in Theoretical Computer Science
[Current]
[General]
[Arrangements]
[Material]
[Schedule]
[Arrangements]
[Literature]
[Links]
Previous years:
[Autumn 2007]
[Spring 2007]
[Autumn 2006]
[Spring 2006]
[Autumn 2005]
[Spring 2005]
[Autumn 2004]
[Spring 2004]
[Autumn 2003]
[Spring 2003]
[Autumn 2002]
[Spring 2002]
[Autumn 2001]
[Spring 2001]
 [12 May 2008] The seminar for this Spring is over;
many thanks for your active participation.
The grade sheet for the seminar is available
here.
 [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 T0.7050 "Introduction to Postgraduate
Studies in Computer Science", the time of the
seminar has been changed from Monday 4:307 p.m.
to Thursday 4:307 p.m., with a few exceptions.
(See detailed schedule
below.)
 [27 Dec 2007] The first seminar session is on Mon 21 Jan.
Registration via
TOPI.
 Time, place:
Mondays 4:307 p.m.
Thursdays 4:307 p.m.,
seminar room TB353.
First session Mon 21 Jan.
 Coordinator:
Prof. Pekka Orponen,
room TA348.
 Registration by
TOPI.
 Prerequisites:
First two years' mathematics courses
including introductory discrete mathematics
(Mat1.2991), and basic knowledge of the design
and analysis of algorithms (T106.1220/1223).
Familiarity with advanced algorithmic techniques
(T79.4201, T106.4100), computational complexity theory
(T79.5103), and optimisation theory (Mat2.2105, Mat2.3140)
will help in assimilating the material and setting it in
a broader context.
 Credits:
Each fullsession 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:
V. Vazirani:
Approximation Algorithms
(SpringerVerlag, 2001).
Two copies of the book will be available for shortterm loan
and one for readingroom 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),
Siert Wieringa
Presentation:
slides,
feedback form
 14 Feb:
Basic Problems 2: Multiway Cut, kCut, kCenter (Chs. 4, 5),
Olli Pottonen
Presentation:
slides,
feedback form
 21 Feb:
Basic Problems 3: Knapsack, Bin Packing, Scheduling (Chs. 8, 9, 10),
Petri Savola
Presentation:
slides,
feedback form
 25 Feb (Monday!):
Linear Programming and LP Duality (Ch. 12),
Alexey Kirichenko
Presentation:
slides,
feedback form
 10 Mar (Monday!):
LP Techniques for Set Cover (Chs. 13, 14, 15),
Risto Hakala
Presentation:
slides,
feedback form
 13 Mar:
LP Techniques for Satisfiability and Scheduling (Chs. 16, 17),
Siert Wieringa
Presentation:
slides,
feedback form
 20 Mar:
Easter break; no seminar.
 27 Mar:
LP Techniques for Multicuts and Multicommodity Flows (Chs. 18, 20),
André Schumacher
Presentation:
slides,
feedback form

31 Mar 7 Apr (Monday!):
LP Techniques for Steiner Forests and Networks (Chs. 22, 23)
Alexey Kirichenko 
Presentation:
slides,
feedback form
Pekka Orponen 
Presentation:
slides,
feedback form
 10 Apr:
LP Techniques for Facility Location and kMedians (Chs. 24, 25),
Risto Hakala
Presentation:
slides,
feedback form
 17 Apr: No seminar.

17 Apr 24 Apr: Semidefinite Programming (Ch. 26),
Pekka Orponen
Presentation:
slides,
feedback form
 28 Apr (Monday!):
Hardness of Approximation (Ch. 29),
Olli Pottonen
Presentation:
slides,
feedback form
 5 May (Monday!):
The Shortest Vector Problem (Ch. 27),
Alexey Kirichenko
Presentation:
slides,
feedback form
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,
SpringerVerlag 1999.
 D. S. Hochbaum (Ed.),
Approximation Algorithms for NPHard Problems,
PWS Publishing 1997.
 J. Hromkovic,
Algorithmics for Hard Problems: Introduction to Optimization,
Randomization, Approximation, and Heuristics, 2nd Ed.,
SpringerVerlag 2003.
[TCS main]
[Contact Info]
[Personnel]
[Research]
[Publications]
[Software]
[Studies]
[News Archive]
[Links]
Latest update: 12 May 2008.
Pekka Orponen
