

























Fair resource allocation is a fundamental optimization problem with applications in operations research, networking, and economic and game theory. Research in these areas has led to the general acceptance of a class of $α$-fair utility functions parameterized by $α\in [0, \infty]$. We consider $α$-fair packing -- the problem of maximizing $α$-fair utilities under positive linear constraints -- and provide a simple first-order method for solving it with relative-error guarantees. The method has a significantly lower convergence time than the state of the art, and to analyze it, we leverage the Approximate Duality Gap Technique, which provides an intuitive interpretation of the convergence argument. 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 near-linear-time solvers with relative-error guarantees.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。