Bounding the Price-of-Fair-Sharing using Knapsack-Cover Constraints to guide Near-Optimal Cost-Recovery Algorithms

Sander Aarts, Jacob Dentes, Manxi Wu +1

We consider the problem of fairly allocating the cost of providing a service among a set of users, where the service cost is formulated by an NP-hard {\it covering integer program…