An exact algorithm for a problem on allocating indivisible goods under min-max fairness constraints


We provide an exact algorithm for allocating a collection of indivisible goods to multiple agents under production-demand constraints and min-max fairness criterium, i.e., the resulting allocation must ensure that all agents are (approximately) equally satisfied. The starting point for this investigation was an enterprise’s problem on allocating its vehicle production among its dealership network while trying to maximize potential revenue. We also illustrate our algorithm’s behavior on real data and discuss some future research directions.

Proceedings of the XXXVII Congress of the Brazilian Society for Computing (2017)

(in portuguese: Método Exato para Um Problema de Alocação Justa)