Fetching the paper…

Reading the bibliography…

2018

Fair Packing and Covering on a Relative Scale

Diakonikolas, Jelena, Fazel, Maryam, Orecchia, Lorenzo

Original
PDF
Post on X

Understand

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 $\alpha$-fair utility functions parameterized by $\alpha \in [0, \infty]$.
We consider $\alpha$-fair packing -- the problem of maximizing $\alpha$-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.

Fair Packing and Covering on a Relative Scale · Around

Built on

J. F. Nash Jr
1950
Earlier work this paper cites.
A. B. Atkinson
1970
Earlier work this paper cites.
D. P. Bertsekas
1971
Earlier work this paper cites.
E. Kalai and M. Smorodinsky
1975
Earlier work this paper cites.
M. Luby and N. Nisan
1993
Earlier work this paper cites.
C. Papadimitriou and M. Yannakakis
1993
Earlier work this paper cites.
Y. Bartal, J. Byers, and D. Raz
1997
Earlier work this paper cites.
J. Mo and J. Walrand
2000
Earlier work this paper cites.
N. Young
Original
2001
Earlier work this paper cites.
S. Low, F. Paganini, and J. Doyle
2002
Earlier work this paper cites.
Y. Nesterov
2005
Earlier work this paper cites.

Similar

F. Kuhn, T. Moscibroda, and R. Wattenhofer
2006
Cited alongside, same era.
K. Jain and V. Vazirani
2007
Cited alongside, same era.
B. Awerbuch, Y. Azar, and R. Khandekar
2008
Cited alongside, same era.
B. Awerbuch and R. Khandekar
2009
Cited alongside, same era.
D. P. Bertsekas
2009
Cited alongside, same era.
T. Lan, D. Kao, M. Chiang, and A. Sabharwal
2010
Cited alongside, same era.
D. Bertsimas, V. F. Farias, and N. Trichakis
2011
Cited alongside, same era.

Then

F. Kelly and E. Yudovina
2014
Later among the works it cites.
B. McCormick, F. Kelly, P. Plante, P. Gunning, and P. Ashwood-Smith
2014
Later among the works it cites.
Z. Allen-Zhu and L. Orecchia
2015
Later among the works it cites.
T. Bonald and J. Roberts
2015
Later among the works it cites.
M. W. Mahoney, S. Rao, D. Wang, and P. Zhang
2016
Later among the works it cites.
J. Marasevic, C. Stein, and G. Zussman
2016
Later among the works it cites.
arXiv preprint, arXiv:1710.09002
Original
J. Diakonikolas and L. Orecchia · 2017

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

A. Ghodsi, M. Zaharia, B. Hindman, A. Konwinski, S. Shenker, and I. Stoica

2011

Cited alongside, same era.

D. Bertsimas, V. F. Farias, and N. Trichakis

2012

Cited alongside, same era.

C. Joe-Wong, S. Sen, T. Lan, and M. Chiang

2013

Cited alongside, same era.

A. Beck, A. Nedić, A. Ozdaglar, and M. Teboulle

2014

Cited alongside, same era.

Later among the works it cites.

Y. Nesterov

2018

Closest in time.

J. Diakonikolas and L. Orecchia

2019

Closest in time.

L. Jose, S. Ibanez, M. Alizadeh, and N. McKeown

2019

Closest in time.