Competitive Algorithms for Bulk Allocation under Uncertainty: The Caterer's Problem
Arjun Kodialam · SIAM Undergraduate Research Online · 2020
We consider the problem of allocating resources to meet an uncertain demand.There are well studied approaches to solve this problem when distributional information is known about the demand.We consider this resource allocation problem when we lack information about the statistics of the demand.These types of resource allocation problems, where there is only minimal information available about the demand, arises naturally in many instances.The motivation for studying this problem is the allocation of resources (testing kits, masks) for pandemic control.While resources are being allocated, there is only minimal information known about the demand size.Decision makers have to solve some version of the Caterer's problem when making advance reservation of resources (processing, storage) in the cloud for new applications.We develop deterministic and randomized competitive algorithms for the Caterer's problem.Unlike the closely related online Ski-rental problem, the Caterer's problem does not satisfy the principle of equality and this makes the Caterer's problem more challenging.We prove the optimality of the randomized algorithms by using Yao's Lemma and developing matching lower bounds for the problem.