An algorithm for the fair resource allocation problem with a submodular constraint (Q1179783)

The fair resource allocation problem is to allocate a given amount of discrete resources to a given set of activities in the fairest manner. This problem has recently been generalized to one with submodular constraints. In this paper a new algorithm is proposed that first solves the continuous version and then modifies the continuous solution into an integer optimal solution. It is shown that in some cases the time complexity of the new method is less than that of the previously known algorithms.