The Design of Competitive Online Algorithms via a Primal-Dual Approach

By Niv Buchbinder, Joseph (Seffi) Naor. Foundations and Trends® in Theoretical Computer Science, 2009

424 citations recorded by the source corpus.

Subfields: Computer Networks and Communications, Electrical and Electronic Engineering, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/681cbd76af40bea3c59aa1442326f5271dbd6252

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

1. Satyen Kale
2. Sanjeev Arora
3. Aranyak Mehta
4. Elad Hazan
5. Aleksandrs Slivkins
6. Ching-An Cheng
7. Byron Boots
8. Frédéric Koriche

In Electrical and Electronic Engineering

1. Satyen Kale
2. Sanjeev Arora
3. Aranyak Mehta
4. Elad Hazan

In Management Science and Operations Research

1. Elad Hazan
2. Aranyak Mehta
3. Sanjeev Arora
4. Satyen Kale
5. Zeyuan Allen-Zhu
6. John C. Duchi
7. Aleksandrs Slivkins
8. Vitaly Feldman

Citations in the corpus

• The Multiplicative Weights Update Method: a Meta-Algorithm and Applications (2012, methodology): “We refer the readers to the survey by Buchbinder and Naor [14] for an extensive discussion of the topic.”
• Adaptive Submodularity: Theory and Applications in Active Learning and Stochastic Optimization (2010, neutral): “nts which have appeared so far. Alon et al. (2009) obtain a polylogarithmic approximation to this problem, via an online primal–dual framework which has been profitably applied to many other problems. Buchbinder and Naor (2009) provide a detailed treatment of this framework. Note that competitive ana”
• Online Matching and Ad Allocation (2013, methodology): “In a parallel line of work, the same problems have been solved using the Online Primal–Dual framework (introduced by Buchbinder and Naor [22]).”
• A Dynamic Near-Optimal Algorithm for Online Linear Programming (2009, neutral): “G T ] 1 6 N ov 2 00”