TOP
Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 01231

Design and Analysis of Randomized and Approximation Algorithms

( Jun 03 – Jun 08, 2001 )

Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/01231

Organizers




Motivation

Most computational task that arise in realistic scenarios are intractable, at least if one insists on exact solutions delivered with certainty within a strict deadline. Nevertheless, practical necessity dictates that acceptable solutions of some kind must be found in a reasonable time. Two important means for surmounting the intractability barrier are randomized computation , where the answer is optimal with high probability but not with certainty, or approximate computation , where the answer is guaranteed to be within, say, small percentage of optimality. More often than not, these two notions go hand-in-hand.

The seminar will be concerned with these phenomena. It will address the newest development in the design and analysis of randomized approximation algorithms, and the new fundamental insights into computational approximate feasibility, optimality, and the intractability of various computational problems. The main focus of the workshop is to be on two specific topics and the various interactions between them. The specific topics are the following:

  • Approximation algorithms for optimization problems.
  • Randomization and de-randomizing techniques play a major role here, both in positive (upper bounds) and negative (lower bounds) results. It features for example in the "rounding" step of approximation algorithms based on linear or semidefinite programming relaxations; it is also at the heart of the theory of probabilistically checkable proofs (PCPs) that is the basis for the recent non-approximability results. A number of very significant new results were obtained here recently.
  • Approximation algorithms for measurement problems.
  • The word "measurement" here is used to distinguish a class of problems-determining the cardinality of combinatorially or computationally defined sets, volume, expectation of random variables on configurations of complex systems, etc. - which are very different in flavor of the optimization problems. This theme is less developed than the previous one, but significant progress is currently being made, both in design of efficient approximation algorithms, and in proving the first approximation lower bounds based on the PCP-techniques mentioned before. It is aimed here at investigating further fundamental and intrinsic connections between the efficiency of approximating optimization problems and the efficiency of approximating measurement problems.

The main goal of the seminar is to bring together researchers working in the area of approximation algorithms and approximation complexity of computational problems, and focus on the newest developments (including practical implementations) within, and also in between the above main themes.


Participants
  • Sanjeev Arora (Princeton University, US) [dblp]
  • Alexander Barvinok (University of Michigan - Ann Arbor, US) [dblp]
  • Petra Berenbrink (Simon Fraser University - Burnaby, CA) [dblp]
  • Piotr Berman (Pennsylvania State University - University Park, US)
  • Norbert Blum (Universität Bonn, DE)
  • Christian Borgs (Microsoft Research - Redmond, US)
  • Graham R. Brightwell (London School of Economics, GB)
  • Jennifer T. Chayes (Microsoft Research - Redmond, US) [dblp]
  • Colin Cooper (King's College London, GB)
  • Artur Czumaj (NJIT - Newark, US) [dblp]
  • Martin Dyer (University of Leeds, GB) [dblp]
  • Lars Engebretsen (KTH Royal Institute of Technology, SE)
  • Johannes Fehrenbach (Universität Freiburg, DE)
  • Wenceslas Fernandez de la Vega (Université Paris Sud, FR)
  • Alan M. Frieze (Carnegie Mellon University, US) [dblp]
  • Leslie Ann Goldberg (University of Warwick - Coventry, GB) [dblp]
  • Catherine Greenhill (UNSW - Sydney, AU) [dblp]
  • Mikael Hammar (University of Salerno, IT)
  • Mathias Hauptmann (Universität Bonn, DE)
  • Klaus Jansen (Universität Kiel, DE) [dblp]
  • Thomas Jansen (TU Dortmund, DE) [dblp]
  • Mark R. Jerrum (University of Edinburgh, GB) [dblp]
  • Sampath Kannan (University of Pennsylvania - Philadelphia, US) [dblp]
  • Michal Karonski (University of Poznan, PL)
  • Marek Karpinski (Universität Bonn, DE) [dblp]
  • Sanjeev Khanna (University of Pennsylvania - Philadelphia, US) [dblp]
  • Spyros Kontogiannis (University of Ioannina, GR)
  • Piotr Krysta (TU Dortmund, DE) [dblp]
  • Michael Langberg (CalTech - Pasadena, US)
  • Malwina J. Luczak (University of Oxford, GB)
  • Christine Marikar (Bonn, DE)
  • Claire Mathieu (Brown University - Providence, US) [dblp]
  • Haiko Müller (University of Leeds, GB) [dblp]
  • Bengt Nilsson (Malmö University, SE)
  • Mike S. Paterson (University of Warwick - Coventry, GB) [dblp]
  • Dana Randall (Georgia Institute of Technology - Atlanta, US) [dblp]
  • José Rolim (University of Geneva, CH)
  • Miklos Santha (Université Paris Sud, FR) [dblp]
  • Alexander D. Scott (University College London, GB) [dblp]
  • Jung-Bae Son (University of Edinburgh, GB)
  • Gregory B. Sorkin (IBM TJ Watson Research Center - Yorktown Heights, US) [dblp]
  • Angelika Steger (ETH Zürich, CH) [dblp]
  • Eli Upfal (Brown University - Providence, US) [dblp]
  • Eric Vigoda (University of Chicago, US) [dblp]
  • Peter Wegner (Universität Bonn, DE)
  • David B. Wilson (Microsoft Research - Redmond, US)
  • Gerhard J. Woeginger (TU Eindhoven, NL) [dblp]

Related Seminars
  • Dagstuhl Seminar 9124: Randomized Algorithms (1991-06-10 - 1991-06-14) (Details)
  • Dagstuhl Seminar 05201: Design and Analysis of Randomized and Approximation Algorithms (2005-05-15 - 2005-05-20) (Details)
  • Dagstuhl Seminar 08201: Design and Analysis of Randomized and Approximation Algorithms (2008-05-11 - 2008-05-16) (Details)
  • Dagstuhl Seminar 11241: Design and Analysis of Randomized and Approximation Algorithms (2011-06-13 - 2011-06-17) (Details)