A BRICS Mini-Course
March 7, 12 and 13, 1996
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.
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.
Introduction and Motivation.
Definition of basic concepts: approximability, approximation schemes, etc.
Simple examples of approximable problems:
MAX SNP and L-reductions:
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.