| Summary: | We consider a problem of allocating limited quantities of M types of resources among N independent activities that evolve over T time periods. During each period, a task is assigned to each activity. Each task consumes resources, generates utility, and determines the subsequent state of the activity. The goal is to maximize average utility. We establish that the problem is NP-hard to approximate to within any constant factor. We then propose and study two polynomial-time approximation algorithms which guarantee small performance losses in different regimes. The first leads to an error of no more than UMT/N, where U is the maximal time-averaged utility that can be generated by an activity. The second algorithm promises O(UN ln(MT)/R) loss, where R is the available quantity of the scarcest resource. The first algorithm extends to situations in which, rather than being classified as one among M types, each resource can fill a subset among M roles. |
