7 listopada 2017 10:15
[Seminarium ZOK] Matthias Englert: "Reordering Buffer Management in Trees and General Metric Spaces"
Tytuł: Reordering Buffer Management in Trees and General Metric Spaces
Prelegent: Matthias Englert (University of Warwick)
Czas i miejsce: wtorek, 7-go listopada, 2017, 10:15, sala 119
Abstract:
In the reordering buffer problem, a sequence of items located in a
metric space arrive one-by-one, and have to be processed by a single
server moving within the metric space. At any point in time, the first k
unprocessed items from the sequence are available for processing and the
server has to select one of these items and process it by visiting its
location. The goal is to process all items while minimizing the total
distance the server moves.
The model was introduced as a clean theoretical abstraction of a number
of problems arising in computer science and economics, e.g., disk
scheduling, rendering in computer graphics, or managing paint shops in
automotive manufacturing.
We study online algorithms for this problem, i.e., algorithm that have
no information about future arrivals of items and have to base their
decisions entirely on the past.