Bandwidth-Constrained Allocation in Grid Computing

Grid computing systems pool together the resources of many workstations to create a virtual computing reservoir. Users can “draw” resources from this reservoir using a pay–as–you–go model, commonly used for utilities (electricity and water). We model such a system as a capacitated graph, and study a basic allocation problem: given a set of jobs, each demanding computing and bandwidth resources and yielding a profit, determine which feasible subset of jobs yields the maximum total profit.