https://www.dagstuhl.de/02271

June 30 – July 5 , 2002, Dagstuhl Seminar 02271

Online Algorithms

Organizers

Susanne Albers (Universität Freiburg, DE)
Amos Fiat (Tel Aviv University, IL)
Gerhard J. Woeginger (TU Eindhoven, NL)

For support, please contact

Dagstuhl Service Team

Documents

List of Participants
Dagstuhl-Seminar-Report 347

Seminar Photos

Motivation Text

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.

Related Dagstuhl Seminar

Book exhibition

Books from the participants of the current Seminar 

Book exhibition in the library, ground floor, during the seminar week.

Documentation

In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.

 

Download overview leaflet (PDF).

Publications

Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.

NSF young researcher support