| |
|
The course will take place in room A36 of the IFW building every thursday, 3pm till 5pm, and the exercise course will be from 5pm till 6pm.
Oral exams, by appointment.
Introduction
(Widmayer)We briefly review the concept of NP-completeness and polynomial time transformations between problems. We then introduce the concept of approximation and give classical examples of polynomial time approximation algorithms for NP-hard optimization problems. We discuss the basic notions, such as approximation ratio, inapproximability, and approximation schemes.
Linear Programming Techniques
(Gärtner)Linear programming problems admit polynomial-time solutions, but they are among the difficult problems in the class P. Exactly this feature makes them useful in approximation algorithms. We discuss the techniques of LP relaxation and (randomized) rounding, as well as the primal-dual method.
Non-Approximability
(Cochand)We discuss techniques used to show that it is NP-hard to approximate some specific optimization problems with a given approximation ratio. A basic tool for establishing such results are so-called "gap producing reductions". We shall see that the existence of such reductions is intimately related to the existence of efficient randomized verification prcedures underlying a "probabilistic" characterisation of the class NP: in this context, only a limited number of randomly chosen bits of the certificate witnessing YES-instances need be considered for the verification. The existence of such verification procedures (probabilistically checkable proofs) is the essence of the PCP theorem. We shall prove a weak form of this result (NP in PCP(poly,1)). Finally, we shall use expander-graphs to show that it is NP-hard to approximate MAX-CLIQUE within some power of the node-set cardinality.
For further information please refer to bar.bs, bar.pdf.
The Steiner Tree Problem
(Steger)The central theme of these lectures is a geometrical problem dating back to Jakob Steiner. This problem, now called the Steiner problem, was initially of importance only within the context of land surveying. In the last decade, however, applications as diverse as VLSI-layout and the study of phylogenetic trees lead to a significant rise in the interest of this problem. The resulting progress has uncovered fascinating connections to and among graph theory, the study of algorithms, and complexity theory. In these lecture we will show how various techniques and concepts which were introduced in previous lectures can be applied to design efficient approximation algorithms for various instances of the Steiner tree problem.
For additional information please refer to approx-steiner.ps, approx-steiner.pdf.
Graph Problems
(Erlebach)In the first part of the lecture, we deal with the shifting strategy, which is a general technique for obtaining polynomial-time approximation schemes for Maximum Independent Set and other optimization problems on certain classes of graphs. We will see how this strategy can be applied to geometric intersection graphs in order to solve problems motivated by cellular networks and by map labelling. In the second part of the lecture, we deal with path problems in graphs such as the edge-disjoint paths problem, the path coloring problem, and the unsplittable flow problem.
For more information about this part of the lecture please refer to http://www.tik.ee.ethz.ch/~erlebach/approx/.