Return of the Boss Problem: Competing Online against a Non-adaptive Adversary

摘要

We follow the travails of Enzo the baker, Orsino the oven man, and Beppe the planner. Their situation have a common theme: They know the input, in the form of a sequence of items, and they are not computationally constrained. Their issue is that they don't know in advance the time of reckoning, i.e. when their boss might show up, when they will be measured in terms of their progress on the prefix of the input sequence seen so far. Their goal is therefore to find a particular solution whose size on any prefix of the known input sequence is within best possible performance guarantees.