Approximation: Theory and Algorithms

Peter Widmayer, widmayer@inf.ethz.ch
Bernd Gärtner, gaertner@inf.ethz.ch
Johannes Blömer, bloemer@uni-paderborn.de
Maurice Cochand, cochand@ifor.math.ethz.ch

Invited Speakers

Angelika Steger, steger@informatik.tu-muenchen.de
Thomas Erlebach erlebach@tik.ee.ethz.ch

Assistant

József Solymosi, solymosi@inf.ethz.ch

Topics and Abstracts

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.

Selected Applications

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 path problems in graphs such as the edge-disjoint paths problem, the path coloring problem, and the unsplittable flow problem.

Where and When

The course will take place in room B42 of the IFW building (consult map). During the five weeks of January 8 through February 9, the course will be held Thursdays and Fridays, 9am till 6pm. Participants are not required to sign up for the course. However, sporadic participation is discouraged.

Schedule

The first four weeks are covered by the instuctors, while the selected topics are taught by the invited speakers during the last week. For a rough schedule, we will start 9:15 in the morning with up to three hours of lectures (some time might also be devoted to exercises in the morning session). After lunch, we continue with lectures and exercises. The day will be concluded by a discussion of material and exercises, at around 5-6pm.

Exam

Oral exams, by appointment.

Some Online Material

Hardness of Approximations. Chapter in Approximation Algorithms for NP-hard Problems , Dorit Hochbaum, 1996.

A compendium of NP optimization problems. Chapter in Complexity and Approximation by G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi 1999.

The Approximability of NP-hard problems. by Sanjeev Arora, Survey based upon a plenary lecture at ACM STOC'98.

Einführung in Graphen und Algorithmen by Thomas Emden-Weinert,Stefan Hougardy, Bernd Kreuter, Hans Jürgen Prömel and Angelika Steger. 1996.