CENTER FOR ALGORITHMIC SYSTEMS
MSc Programme ``Algorithmic Systems"
Course: Approximation algorithms (Benaderingsalgoritmen, BA)
Designing software or systems is a matter of designing suitable algorithmic
models and solving them, and casting the solutions into programs afterwards.
While there are many algorithmic models (shortest path, minimum spanning
trees, convex hulls, data searching) are easy to solve, the vast majority of
problems in industrial practice are not. The modern approach is to try and find
acceptable approximate solutions, using algorithms that are `quick and simple'
and yet deliver answers of a quality that is good enough for practical purposes.
Common techniques that are used involve e.g. linear programming relaxation,
random sampling, and local search. This course gives an introduction to the
design of approximation algorithms, with examples concerning network models and
discrete optimization. The course will also show the limitations of
approximation: there are problems that appear to be so hard that even
approximate solutions seem impossible to find efficiently (in large problem
The course is part of the MSc program `Algorithmic Systems'. However, in
2002/03 the course will serve two groups of students: third year
students in `Informatics and Management' who need to do this course as part
of their required program, and masterstudents who do this course as
part of their masterprogram (in Algorithmic Systems or another program).
The lectures are the same for both groups, but the further requirements
differ: third year students need to write a paper, the masterstudents work on
research issues in a separate working group (the precise form will depend on
the number of participants). The final exam is again joint.
J. Hromkovic, Algorithms for hard problems - Introduction to combinatorial
optimization, randomization, approximation and heuristics, 2nd edition,
Springer-Verlag, Berlin, 2003. ISBN 3-540-44134-4
Order the book in time, e.g. electronically from www.Springer.de or
Amazon(.de). Order the second edition of the book. (The first edition
was used last year. In the 2nd edition many corrections were included and some
50 pages of new material was added.)
A course on `advanced' algorithms (like `Algoritmiek'), and a
course in (discrete) optimization.
For masterstudents: the course on `Algorithmic modelling and complexity' is
recommended but not required. The background needed from this course
will be recovered in the first two lectures.
The relevant parts of the book by J. Hromkovic will be studied. The
general part of the course is intended for all participants. Masterstudents
will work on research-oriented issues in a separate working group or seminar.
The course consists of:
For errata to the first and second editions of the book, see the
homepage of the book.
For every lecture the material that needs to be studied is listed in the
weekly werkschedule: study the material both
in advance (globally) and afterwards (in detail). All further assignments are
listed in the weekly schedule as well.
- For 3rd year students: paper.
- For masterstudents: (joint) research group or seminar.
Final exam (tentamen): Monday, 24 Februari 2003, 14.00-17.00, in EDUC-ALFA.
Here are some old exams (in Dutch), based on a previous version of the
course and partly based on another textbook. The old exams are
NOT necessarily representative as to contents.
- 21 December 2000: (ps),
14 March 2001: (ps),
-   1 March 2002:
8 May 2002:    (ps), (pdf).
For 3rd year students: the `paper' and the exam will each count for 50% of the
For masterstudents: the working group/seminar part will count for 40%, the
participation (in the working group) for 10%, and the exam will count for
50% of the final grade.
To search for documentation, use the:
Last modified: December 2002