The Fair Resource Allocation Problem with Submodular Constraints
Satoru Fujishige, Naoki Katoh, Tetsuo Ichimori · Mathematics of Operations Research · 1988
The problem of allocating a limited resource to relevant activities in a fair manner on the basis of a certain general objective function has recently been considered by N. Katoh, T. Ibaraki, and H. Mine. We generalize Katoh, Ibaraki, and Mine's problem to the one with a feasible region expressed by a submodular function and give an efficient solution algorithm. The proposed algorithm is of the same complexity as and simpler than Katoh, Ibaraki, and Mine's when specialized to their problem.