TCS / Studies / T-79.7001 Postgraduate Course in Theoretical Computer Science

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 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 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

[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]

Current

[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 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 below.)
[27 Dec 2007] The first seminar session is on Mon 21 Jan. Registration via TOPI.

General

Time, place: ~~Mondays 4:30-7 p.m.~~ Thursdays 4:30-7 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 (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.
Credits: 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.

Arrangements

The presenter's archivable slides (preferably in PDF) will be linked to the schedule below by the coordinator.

Seminar material

The seminar will be based on the textbook:

V. Vazirani: Approximation Algorithms (Springer-Verlag, 2001).

Two copies of the book will be available for short-term loan and one for reading-room use in the DCSE library.

Schedule

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, k-Cut, k-Center (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 k-Medians (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

Literature

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, Springer-Verlag 1999.
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., Springer-Verlag 2003.