Resource allocation under limited sharing

AbstractWe study the problem of resource sharing within a system of users, each with the same resource capacity, but with varying resource demands. For model simplicity, we assume system saturation, so that the total demand matches the total capacity, and permit only a limited form of sharing in which a user is free to share its unused capacity with exactly one other user. We seek to maximize the total amount of unshared capacity over all feasible solutions, reflecting an environment in which sharing incurs a cost proportional to the overall quantity shared. For the general problem, which is NP-hard, we derive a tight worst-case performance bound for a greedy algorithm G as well as for a number of other sharing rules. We also prove several results concerning G's behavior in more restricted settings