Approximation: Theory and Algorithms

Johannes Blömer, bloemer@uni-paderborn.de
Maurice Cochand, cochand@ifor.math.ethz.ch
Thomas Erlebach , erlebach@tik.ee.ethz.ch
Bernd Gärtner, gaertner@inf.ethz.ch
Angelika Steger , steger@informatik.tu-muenchen.de
Peter Widmayer, widmayer@inf.ethz.ch

Teaching Assistant

Uli Wagner, uli@inf.ethz.ch

Schedule

This is a 5-week block course, from 10 January to 8 February, 2002. It will take place on Thursdays and Fridays, from 9am to 6pm. Generally, we will start at 9:15 in the morning, with up to three hours of lectures. After lunch, we continue with lectures and exercises. The day will be concluded by a discussion of material and exercises, at around 5-6 pm.

Participants are not required to sign up for the course. Please note, however, that merely sporadic participation is strongly discouraged.

Here is an outline of the course (see below for short summaries):

10 - 11 January: Peter Widmayer, Introduction
17 - 18 January: Bernd Gärtner, Linear Programming Techniques
24 - 25 January: Johannes Blömer, Semidefinite Programming and Lattices
31 January: Angelika Steger, The Steiner Tree Problem
1 February: Thomas Erlebach, Graph Problems
7 - 8 February: Maurice Cochand, Non-Approximability

Location

Room B42 of the IFW building.

Topics and Abstracts

Introduction (Peter 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 (Bernd 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 (Johannes 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.

The Steiner Tree Problem (Angelika 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 (Thomas 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.

Non-Approximability (Maurice 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.

Assignment 1, Assignment 2

Assignment 3, Assignment 4

Assignment 8

Exam

Oral exams on Monday, 11 February, 2002

Recommended Background Reading and References

NP-Hardness

Christos H. Papadimitriou, Complexity Theory, Addison Wesley, 1994

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.

Linear Programming

Christos H. Papadimitriou and Kennesth Steiglitz, Combinatorial Optimization, Dover, 1998

Semidefinite Programming and Lattices

László Lovász, An Algorithmic Theory of Numbers, Graphs and Convexity, SIAM, 1986.

Graph Problems

Thomas Erlebach, Klaus Jansen and Eike Seidel, Polynomial-Time Approximation Schemes for Geometric Graphs, Proceedings of the Twelth Annual ACM-SIAM Symposium on Discrete Algorithms, 2001.

Thomas Erlebach's slides on The Shifting Strategy and on Path Problems in Networks

Clemens Gröpl, Stefan Hougardy, Till Nierhoff and Hans Jürgen Prömel, Approximation algorithms for the Steiner tree problem in graphs. Survey paper, 2001.

Non-Approximability

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

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

Stefan Hougardy, Hans-Jürgen Prömel and Angelika Steger, Probabilistically checkable proofs and their consequences for approximation algorithms. Survey, 1995.