Wednesday, April 13, 2016
12:00 pm

Rigorous Systems Research Group (RSRG) Seminar

A Fast Distributed Algorithm for α-Fair Packing Problems
Jelena Marašević, Electrical Engineering, Columbia University


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 talk, I will present a fast distributed algorithm for weighted α -fair packing problems, that is, the problems of maximizing the objective functions Σj wj xj1- α /(1- α) when α ≠ 1 and Σ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. The algorithm uses simple local update rules, and is stateless (namely, it allows asynchronous updates, is self-stabilizing, and allows incremental and local adjustments). The algorithm converges to approximate solutions in running times that have an inverse polynomial dependence on the approximation parameter ɛ and poly-logarithmic dependence on the problem size. These are the best convergence times known for these problems. Time-permitting, I will also talk about our structural results that characterize the behavior of α-fair allocations in the asymptotic cases when α tends to zero, one, or infinity. 

The talk is based on a recent joint work with Cliff Stein and Gil Zussman.

 

Contact Sydney Garstang sydney@caltech.edu
Add this event to my calendar