In dynamic allocation items arrive and depart randomly and while present are stored in a limited facility; the job of an allocation algorithm is to decide whether and where to store an arriving item, while trying to minimize the cost incurred by rejections. Ordinarily, to prove the value of such an algorithm, one must either Ε½ . assume a specific arrival distribution e.g., Poisson-, or try to obtain bounds Ε½ . relative to an adversary as in competitive analysis .
We present here a novel method of proving precise optimality for certain kinds of dynamic allocation algorithms, without assuming a specific arrival distribution. We do need to assume memoryless departure for at least some item types, and most importantly, we must assume conditions are such that it is not right to reject arrivals unnecessarily.
The method is applied to two simple call assignment problems which arose, in quite different circumstances, at Lucent Technologies. In both cases the method was successful in showing that the intuitively best assignment algorithm really does minimize expected cost under fairly general, and essentially necessary, assumptions.