Approximation Algorithms for Combinatorial Optimization - 0365.4042
Time and Place
Course not given in 2009/10.
Intended Audience and Prerequisites
This is a graduate core course in the M.Sc. program
in Operations Research. It also fits graduate students from other
programs such as Computer Science and Industrial Engineering.
Third year undergraduate students are welcome.
Course requirements/Exams
Weekly homework sets will be assigned during the semester. These
assignments are mandatory.
Solutions to the most
interesting/difficult problems will be discussed in class.
The grade will mainly be determined by the final exam.
There is no textbook.
Course description
Most of the interesting optimization problems which involve
binary or integer variables are NP-hard and do not have `efficient'
algorithms. The subject of constructing approximation
algorithms with provable error bounds for these problems
is nowadays a `hot' research area
and exciting developments are announced frequently.
To see the richness of the area you are invited to look at
`A compendium of NP optimization problems'
http://www.nada.kth.se/theory/problemlist.html
where hundreds of problems are surveyed.
Much of the beauty of these results is in the fact that they are
ingenuous, require very little background knowledge,
differ from each other, and no general theory seems to
unify them. This explains why the topic is popular among students
and researchers, possibly beyond proportion to its real significance
in Operations Research and Computer Science.
The course will survey many problems which were selected
because they are fundamental, have especially nice solutions, or
related to my research.
It will also survey heuristics and
meta-heuristics that are used in practically solving such
problems.