Complexity of the Resource Allocation/Matching Problem with Weight Based Ceilings

摘要

Assigning elements of one set to elements of another set is a common occurrence. This has to be done so that certain objectives are met. In some situations, matching between two different sets is done according to preferences of either one set or both. At the same time, in many cases, a ceiling beyond which the allocations can no longer be made exist. Oftentimes, such a ceiling is made on numbers not on weights (for homogeneous tasks/actors, numbers and weights are synonymous). In this paper, we consider allocations where the tasks and actors are not necessarily homogeneous and the allocation ceilings are based on weights rather than numbers. We develop the algorithm using the Gale and Shapely algorithm for the stable marriage problem as the novel set up. We show that the problem can be solved in polynomial time with worst case being quadratic and best case being linear. We also make sensitivity studies on selected parameters.