18.09.2001

The Workshop was concerned with the newest development in the design and analysis of randomized and approximation algorithms. The main focus of the workshop was on two specific topics: approximation algorithms for optimization problems, and approximation algorithms for measurement problems, and the various interactions between them. Here, new important paradigms have been discovered recently connecting probabilistic proof verification theory to the theory of approximate computation. Also, some new broadly applicable techniques have emerged recently for designing efficient approximation algorithms for a number of computationally hard optimization and measurement problems. This workshop has addressed the above topics and also fundamental insights into the new paradigms and design techniques. The workshop was organized jointly with the RAND-APX meeting on approximation algorithms and intractability and was partially supported by the IST grant 14036 (RAND-APX).