Approximation Algorithms for NP-Hard Problems

Abstract

It is an interesting artifact that most computational tasks today that arise in realistic scenarios are intractable, at least if one insists on delivering exact solutions with certainty within a strict deadline. An important mean for surmounting this intractability barrier is that of approximate computation, where the answer is guaranteed to be within some small fraction of optimality. One of the great recent successes in that area has been the discovery of a new paradigm connecting probabilistic proof verification theory to the theory of approximate computation as well as some new probabilistic combinatorial and algebraic paradigms in designing efficient approximation algorithms.

The workshop was concerned with the most important recent developments in the area of efficient approximation algorithms for NP-hard optimization problems as well as with new techniques for proving intrinsic lower bounds for efficient approximation.

In addition to 25 lectures delivered at general sessions, there were several additional lectures given at the special sessions and the evening problem session. The Program of the meeting and Abstracts of all talks are listed in the subsequent sections of this report. The special sessions were on the following topics:

• Steiner Tree and Related Optimization Problems.
• Query Efficient PCPs.
• Routing Problems in Distributed Networks.
• New PCP Results.
• Approximating Combinatorial Auctions Without Randomized Rounding.

The meeting was held in very informal and stimulating atmosphere. The ad hoc organized special sessions were extraordinarily interesting and intensive venues for communicating most recent results. Thanks to everybody who contributed to the success of this meeting and made it such an enjoyable event!

The organizers and participants thank the Mathematisches Forschungsinstitut Oberwolfach for its help in organizing this conference.

Special thanks go to Mathias Hauptmann for his help in editing this proceedings. We are also indebted to Christiane Andrade, Cornelia Kaufmann, Martin Löhnertz, Ignatios Souvatzis and Claus Viehmann for their continuous support in organizing this conference.