Lower Bounds for the Fair Resource Allocation Problem

Abstract : The α-fair resource allocation problem has received remarkable attention and has been studied in numerous application fields. Several algorithms have been proposed in the context of α-fair resource sharing to distributively compute its value. However, little work has been done on its structural properties. In this work, we present a lower bound for the optimal solution of the weighted α-fair resource allocation problem and compare it with existing propositions in the literature. Our derivations rely on a localization property verified by optimization problems with separable objective that permit one to better exploit their local structures. We give a local version of the well-known midpoint domination axiom used to axiomatically build the Nash Bargaining Solution (or proportionally fair resource allocation problem). Moreover, we show how our lower bound can improve the performances of a distributed algorithm based on the Alternating Directions Method of Multipliers (ADMM). The evaluation of the algorithm shows that our lower bound can considerably reduce its convergence time up to two orders of magnitude compared to when the bound is not used at all or is simply looser.
Document type :
Conference papers
Complete list of metadatas

Cited literature [10 references]  Display  Hide  Download

https://hal.inria.fr/hal-01706142
Contributor : Konstantin Avrachenkov <>
Submitted on : Saturday, February 10, 2018 - 5:47:20 PM
Last modification on : Wednesday, October 10, 2018 - 10:09:37 AM

File

allybokus2017lower(1).pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01706142, version 1

Collections

Citation

Zaid Allybokus, Konstantin Avrachenkov, Jérémie Leguay, Lorenzo Maggi. Lower Bounds for the Fair Resource Allocation Problem. IFIP Performance 2017 - 35th International Symposium on Computer Performance, Modeling, Measurements and Evaluation, Nov 2017, New York, United States. pp.1-7. ⟨hal-01706142⟩

Share

Metrics

Record views

126

Files downloads

131