Width-Independence Beyond Linear Objectives: Distributed Fair Packing and Covering Algorithms
share
In network routing and resource allocation, α-fair utility functions are concave objective functions used to model different notions of fairness in a single, generic framework. Different choices of the parameter α give rise to different notions of fairness, including max-min fairness (α = ∞), proportional fairness (α=1), and the unfair linear optimization (α = 0). In this work, we consider α-fair resource allocation problems, defined as the maximization of α-fair utility functions under packing constraints. We give improved distributed algorithms for constructing ϵ-approximate solutions to such problems. Our algorithms are width-independent, i.e., their running time depends only poly-logarithmically on the largest entry of the constraint matrix, and closely matches the state-of-the-art guarantees for distributed algorithms for packing linear programs, i.e., for the case α = 0. The only previously known width-independent algorithms for α-fair resource allocation, by Marasevic, Stein, and Zussman, obtained convergence times that exhibited much worse dependence on ϵ and α and relied on a less principled analysis. By contrast, our analysis leverages the Approximate Duality Gap framework of Diakonikolas and Orecchia to obtain better algorithms with a (slightly) simpler analysis. Finally, we introduce a natural counterpart of α-fairness for minimization problems and motivate its usage in the context of fair task allocation. This generalization yields α-fair covering problems, for which we provide the first width-independent nearly-linear-time approximate solvers by reducing their analysis to the α < 1 case of the α-fair packing problem.
READ FULL TEXT