|
|
|
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.
Semidefinite Programming and Lattices
(Blömer)We show how to solve NP-hard optimization problems using semi-definite programming. This method is a generalization of the linear programming techniques. We demonstrate the usefulness of this technique on the Max-SAT problem, and on the problem of coloring a 3-colorable graph. Because the latter problem has some interesting complexity-theoretic properties, we discuss it in some detail.
We also discuss the LLL-algorithm to find an approximately shortest vector in a lattice. We present the basic ideas of the LLL-algorithm and show how it can be used to detect weaknesses in some variants of the RSA cryptosystem.
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.
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.
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 interval selection problems and discuss approximation algorithms that are based on linear programming.