This suggest the following abstract model for tasks which are better done in batches than separately.
W = long-run average cost per unit timearising from the waiting time costs. Let \(W_*\) be the minimum, over all online algorithms, of W, and assume \(W_*\) is finite. The value of \(W_*\) and the optimal algorithm depend in some complicated way on the functions \(S(\cdot )\) and \(c(\cdot )\).
Problem: Is there some explicit algorithm (depending of course on \(S(\cdot )\) and \( c(\cdot ))\) and a constant C such that the W for this algorithm satisfies \( W/W_* < C \) for all \(S(\cdot )\) and \( c(\cdot ))\)?
Conceptually, I guess that at both ends (light traffic or heavy traffic) some simple algorithm would work; the issue in the intermediate case. This paper shows that in the \(c = 1\) context, the greedy algorithm (put everything in one batch) has finite W whenever any algorithm does.
History. Problem posted March 2009.
Back to Open Problem list