How the Experts Algorithm Can Help Solve LPs Online
Authors:
- 1 November 2016
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 41 (4) , 1404-1431
Abstract
We consider the problem of solving packing/covering LPs online, when the columns of the constraint matrix are presented in random order. This problem has received much attention, and the main focus is to figure out how large the right-hand sides of the LPs have to be (compared to the entries on the left-hand side of the constraints) to allow (1 + ɛ)-approximations online. It is known that the right-hand sides have to be Ω(ɛ−2 log m) times the left-hand sides, where m is the number of constraints. In this paper, we give a primal-dual algorithm that achieves this bound for mixed packing/covering LPs. Our algorithms construct dual solutions using a regret-minimizing online learning algorithm in a black-box fashion, and use them to construct primal solutions. The adversarial guarantee that holds for the constructed duals helps us to take care of most of the correlations that arise in the algorithm; the remaining correlations are handled via martingale concentration and maximal inequalities. These ideas lead to conceptually simple and modular algorithms, which we hope will be useful in other contexts.Keywords
All Related Versions
This publication has 25 references indexed in Scilit:
- Online Mixed Packing and Covering2013
- Sublinear optimization for machine learningJournal of the ACM, 2012
- Online Learning and Online Convex OptimizationFoundations and Trends in Machine Learning, 2012
- The Design of Competitive Online Algorithms via a Primal—Dual ApproachFoundations and Trends® in Theoretical Computer Science, 2009
- Online auctions and generalized secretary problemsACM SIGecom Exchanges, 2008
- AdWords and generalized online matchingJournal of the ACM, 2007
- Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing ProblemsSIAM Journal on Computing, 2007
- An Analysis of Bid-Price Controls for Network Revenue ManagementManagement Science, 1998
- Finite Exchangeable SequencesThe Annals of Probability, 1980
- On Tail Probabilities for MartingalesThe Annals of Probability, 1975