Approximation Algorithms

Course Contents

Almost-solving problems

The theory of NP-completeness allows us to argue that many important, real-life problems do not have efficient exact solutions. While this may please the theoretician, the message, to most other people, is depressing.

There is hope, however, and the word ``exact'' is the key: the theory tells us nothing about the hardness of finding an approximate solution, e.g. a travelling salesman-tour within 1/1000 millimeters of the optimal! And such a solution may be all we need; it certainly beats algorithms like ``do an exaustive search'' or ``give up''.

The focus of this course will be some very recent breakthroughs in concepts and techniques leading to vastly improved upper and lower bounds for a wide spectrum of approximation problems. In particular, on the side of upper bounds, the course will cover the technique of semi-definite programming applied to combinatorial optimization problems, and on the side of lower bounds the course will show how the results on the so-called ``holographic'' proof systems imply strong negative results on approximating problems falling in a broad complexity class.

Also, at least to the arrangers, the theory of approximation algorithms shows theoretical computer science at its best: it combines beautiful mathematics with the aim of efficiently solving realistic problems.

About the Lecturer

Alessandro Panconesi received his Ph.D. in Computer Science from Cornell University in 1993. His thesis entitled Locality in Distributed Computing included work from a paper that won the Best Student Paper Award at the 1992 STOC. After returning to Europe, Alessandro held an ERCIM Fellowship, spending 6 months each at Amsterdam, Trondheim and Stockholm. He is currently holding a von Humboldt Fellowship at Freie Universitat, Berlin.

Programme

Thursday March 7, 1996, 12:15-14:00 in Colloquium B4

The aim is to present a picture of the situation before the recent breakthroughs.

Introduction and Motivation.
Definition of basic concepts: approximability, approximation schemes, etc.
Simple examples of approximable problems:

1. Min Vertex Cover
2. TSP with triangle inequality

   Thursday March 7, 1996, 15:15-17:00 in Colloquium B4

   Simple hardness proofs:

   1. TSP
   2. self-improvability of Clique Example of PTAS: Scheduling
      Example of FPTAS: Knapsack

      Tuesday March 12, 1996, 10:15-12:00 in Colloquium B4

      Survey of some important results obtained after recent breakthroughs in upper- and lower-bounding techniques. Full proofs will be given.

      MAX SNP and L-reductions:

      1. definition of class MAX SNP and L-reduction
         
      2. MAX SNP-hardness of Max 3Sat (maybe not)
      3. Examples of L-reductions:
         Max Sat-B via expanders, Max Cut

         Tuesday March 12, 1996, 14:15-16:00 in Colloquium B4

         PCP and lower bounds:

         1. definition of PCP
         2. hardness of Clique
         3. hardness of Max 3Sat
         4. hardness of Chromatic Number

            Wednesday March 13, 1996, 10:15-12:00 in Colloquium B4

            Survey of breakthroughs continues.

            Max Sat via randomised rounding
            Max Cut via semi-definite programming

            Wednesday March 13, 1996, 14:15-16:00 in Colloquium B4

            Set Covering:
            

            1. O(log n) approximation via greedy algorithm and primal-dual
            2. thight lower bound via interactive proof systems

References

Prerequisites

The course aims at introducing the non-expert to the field. Knowledge of algorithms and complexity comparable to, say, Sven Skyums course dAlg certainly suffices. One may want to browse through Chapter 13 of Papadimitrious book on Computational Complexity for a sneak preview; but be warned that the focus of the course will be somewhat different from Papadimitriou's.

Erich Meineche Schmidt's Fall course in 1994 and 1995 featered a glimpse of some of the lower bounds in connection with interactive proof systems. These results will be covered in the course.