UU
HOME cs.uu.nl

CENTER FOR ALGORITHMIC SYSTEMS

MSc Programme ``Algorithmic Systems" 2002-2003

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 instances).

Lecturer(s):

Course overview

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.

Class schedule

Text (required)

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 (see here).

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

Prerequisites

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.

Course Work

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:

  1. Lectures

    For errata to the first and second editions of the book, see the homepage of the book.

  2. Homework/Studies

    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.

  3. Research-assignment


  4. Final exam

    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.

Grading

For 3rd year students: the `paper' and the exam will each count for 50% of the final grade.
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.

Search tools

To search for documentation, use the:

Useful links

Other links


Last modified: December 2002