Optimality and Greed in Dynamic Allocation

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 minimmize 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-lambda), 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.