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 02271

Online Algorithms

( Jun 30 – Jul 05, 2002 )

(Click in the middle of the image to enlarge)

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

Organizers




Motivation

In the past twenty years, researchers in Combinatorial Optimization and in Theoretical Computer Science have spent considerable effort on resolving the computational complexity status of various algorithmic problems with respect to finding an optimal solution. Most standard problems have been catalogued by now as either being NP-hard or as being solvable in polynomial time. Now, how should one proceed, if one encounters an NP-hard problem? One approach is to study the behaviour of so-called heuristics, "quick-and-dirty" algorithms which return feasible solutions that are not necessarily optimal. Such heuristics can be empirically valuable methods for attacking an NP-hard optimization problem, especially if the returned solutions are guaranteed to be not too far away from being optimum. Heuristics with some guaranteed worst case behaviour are called approximation algorithms.

Approximation algorithms may be further classified into off-line and into online algorithms. Off-line algorithms solve a problem with full knowledge of the complete problem data. Online algorithms construct partial solutions with partial knowledge of the problem data, and update their solutions everytime some new information is provided. In other words, they must handle a sequence of closely related and interleaved subproblems, satisfying each subproblem without knowledge of the future subproblems. Standard examples of online problems include scheduling the motion of elevators, finding routes in networks and allocating cache memory. Clearly, online algorithms are able to work in real-time enviroments, whereas off-line algorithms will run into difficulties if the input keeps changing.

The usual (somewhat unfair) way of measuring the quality of an online algorithm is to compare it to the optimal solution of the corresponding off-line problem where all information is available at the beginning. An online algorithm that always delivers results that are only a constant factor away from the corresponding optimum off-line solution, is called a competitive algorithm. Competitive algorithms were first investigated in 1969 in a paper by Graham dealing with online scheduling and in 1974 in the Ph.D. thesis of David Johnson dealing with online bin packing.

The Dagstuhl seminar on the design and analysis of competitive algorithms will communicate new results and continue the momentum in this rapidly developing area.


Participants
  • Susanne Albers (Universität Freiburg, DE) [dblp]
  • Peter Auer (TU Graz, AT) [dblp]
  • Giorgio Ausiello (Sapienza University of Rome, IT) [dblp]
  • Yossi Azar (Tel Aviv University, IL) [dblp]
  • Amotz Bar-Noy (Brooklyn College, US)
  • Luca Becchetti (Sapienza University of Rome, IT) [dblp]
  • Wolfgang Bein (Univ. of Nevada - Las Vegas, US)
  • Avrim Blum (Carnegie Mellon University, US) [dblp]
  • Norbert Blum (Universität Bonn, DE)
  • Joan Boyar (University of Southern Denmark - Odense, DK)
  • Nicolò Cesa-Bianchi (University of Milan, IT) [dblp]
  • Bo Chen (University of Warwick, GB)
  • Marek Chrobak (University of California - Riverside, US) [dblp]
  • Willem de Paepe (TU Eindhoven, NL)
  • Leah Epstein (The Interdisciplinary Center - Herzliya, IL)
  • Thomas Erlebach (University of Leicester, GB) [dblp]
  • Ulrich Faigle (Universität Köln, DE)
  • Lene Monrad Favrholdt (University of Southern Denmark - Odense, DK)
  • Amos Fiat (Tel Aviv University, IL) [dblp]
  • Rudolf Fleischer (Fudan University - Shanghai, CN) [dblp]
  • Andrew V. Goldberg (Microsoft Corp. - Mountain View, US) [dblp]
  • Csanad Imreh (MPI für Informatik - Saarbrücken, DE) [dblp]
  • Sandy Irani (University of California - Irvine, US)
  • Kazuo Iwama (Kyoto University, JP) [dblp]
  • Bala Kalyanasundaram (Georgetown University - Washington, US)
  • Anna R. Karlin (University of Washington - Seattle, US) [dblp]
  • Walter Kern (University of Twente, NL)
  • Alex Kesselman (Tel Aviv University, IL)
  • Hal Kierstead (Arizona State University - Tempe, US)
  • Tracy Kimbrel (IBM TJ Watson Research Center, US)
  • Elias Koutsoupias (University of Athens, GR) [dblp]
  • Sven O. Krumke (TU Kaiserslautern, DE)
  • Lawrence L. Larmore (Univ. of Nevada - Las Vegas, US)
  • Kim Skak Larsen (University of Southern Denmark - Odense, DK)
  • Stefano Leonardi (Sapienza University of Rome, IT) [dblp]
  • Vincenzo Liberatore (Case Western Reserve University - Cleveland, US)
  • Yishay Mansour (Tel Aviv University, IL) [dblp]
  • Alberto Marchetti-Spaccamela (Sapienza University of Rome, IT) [dblp]
  • Friedhelm Meyer auf der Heide (Universität Paderborn, DE) [dblp]
  • Seffi Naor (Technion - Haifa, IL) [dblp]
  • John Noga (California State Univ. - Northridge, US)
  • Diana Poensgen (Wien, AT)
  • Chris N. Potts (University of Southampton, GB)
  • Kirk Pruhs (University of Pittsburgh, US) [dblp]
  • Adi Rosén (Technion - Haifa, IL) [dblp]
  • Baruch Schieber (IBM TJ Watson Research Center - Yorktown Heights, US)
  • Uwe Schwiegelshohn (TU Dortmund, DE) [dblp]
  • Jiri Sgall (Czech Academy of Sciences - Prague, CZ) [dblp]
  • Clifford Stein (Columbia University, US) [dblp]
  • Leen Stougie (TU Eindhoven, NL) [dblp]
  • Tomas Tichy (Czech Academy of Sciences - Prague, CZ)
  • Eric Torng (Michigan State University - East Lansing, US)
  • Gerhard Trippen (HKUST - Kowloon, HK)
  • Patchrawat Uthaisombut (University of Pittsburgh, US)
  • Rob van Stee (KIT - Karlsruher Institut für Technologie, DE) [dblp]
  • Arjen Vestjens (Centre for Quantitative Methods - Eindhoven, NL)
  • Gerhard J. Woeginger (TU Eindhoven, NL) [dblp]
  • Guochuan Zhang (Zheiiang University - Hangzhou, CN) [dblp]

Related Seminars
  • Dagstuhl Seminar 9626: On-line Algorithms (1996-06-24 - 1996-06-28) (Details)