A Fast Distributed Algorithm for α-Fair Packing Problems


May 29, 2015


Jelena Marasevic


Columbia University


Over the past two decades, fair resource allocation problems received considerable attention in a variety of application areas. While polynomial time distributed algorithms have been designed for max-min fair resource allocation, the design of distributed algorithms with convergence guarantees for the more general α-fair allocations received little attention. 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 alpha ≠ 1 and Σj wj ln(xj) when alpha = 1 over linear constraints Ax ≤ b, x ≥ 0, where wj are positive weights and A and b are non-negative. The model of distributed computation is similar to the models used in previous work on packing linear programs and network utility maximization problems. The algorithm uses simple local update rules that mimic a tatonnement process, 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 epsilon and poly-logarithmic dependence on the problem size. These are the best convergence times known for these problems. The talk is based on a recent joint work with Cliff Stein and Gil Zussman.


Jelena Marasevic

Jelena Maraševic is a Ph.D. student at Columbia University. Her research focuses on algorithms for fair resource allocation problems, with applications in wireless networks. She received her B.Sc. degree from University of Belgrade, School of Electrical Engineering, in 2011, and her M.S. degree in electrical engineering from Columbia University in 2012. Jelena is a recipient of the M.S. Award of Excellence and the Jacob Millman Prize for Excellence in Teaching Assistance from Columbia University. She is also a finalist of the Qualcomm Innovation Fellowship 2015 competition.