Nov. 7, 2017, 10:15 a.m.

Title: Reordering Buffer Management in Trees and General Metric Spaces
Speaker: Matthias Englert (University of Warwick)
Time and place: Tuesday, 7th of November, 2017, 10:15 am, room 119.

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.