2015/02/11 by Jelena Marašević, Clifford Stein, Marasevic, Jelena +3
Engineering · #Advanced Manufacturing and Logistics Optimization #Optimization and Packing Problems
paper · pdf · doi:10.48550/arxiv.1502.03372
Over the past two decades, fair resource allocation problems have received considerable attention in a variety of application areas. However, little progress has been made in the design of distributed algorithms with convergence guarantees for general and commonly used α-fair allocations. In this paper, we study weighted α-fair packing problems, that is, the problems of maximizing the objective functions (i) ∑j wj xj1-α/(1-α) when α> 0, α≠ 1 and (ii) ∑j wj ln xj when α= 1, over linear constraints Ax ≤ b, x≥ 0, where wj are positive weights and A and b are non-negative. We consider the distributed computation model that was used for packing linear programs and network utility maximization problems. Under this model, we provide a distributed algorithm for general α that converges to an ε-approximate solution in time (number of distributed iterations) that has an inverse polynomial dependence on the approximation parameter ε and poly-logarithmic dependence on the problem size. This is the first distributed algorithm for weighted α-fair packing with poly-logarithmic convergence in the input size. The algorithm uses simple local update rules and is stateless (namely, it allows asynchronous updates, is self-stabilizing, and allows incremental and local adjustments). We also obtain a number of structural results that characterize α-fair allocations as the value of α is varied. These results deepen our understanding of fairness guarantees in α-fair packing allocations, and also provide insight into the behavior of α-fair allocations in the asymptotic cases α→ 0, α→ 1, and α→ ∞.