An Algorithm for the Equipollent Resource Allocation Problem

The equipollent resource allocation problem asks to allocate a given amount of discrete resources to a given set of activities so that the maximum of the profit differences between activities is minimized. A typical example of this type of allocation problem may be found in the apportionment of a given number of seats to electoral districts. We present here an O(n log n + n log N/n) algorithm to find an optimal solution, where n is the number of activities and N is the amount of resources.