How the experts algorithm can help solve lps online

Anupam Gupta

Research output: Contribution to journalArticlepeer-review

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 41C.5-Approximations online. It is known that the right-hand sides have to be i4.2 logm5 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.

Original languageEnglish (US)
Pages (from-to)1404-1431
Number of pages28
JournalMathematics of Operations Research
Volume41
Issue number4
DOIs
StatePublished - Nov 2016

Keywords

  • Experts Algorithm
  • Linear Programming
  • Online Algorithms
  • Secretary Problem

ASJC Scopus subject areas

  • General Mathematics
  • Computer Science Applications
  • Management Science and Operations Research

Fingerprint

Dive into the research topics of 'How the experts algorithm can help solve lps online'. Together they form a unique fingerprint.

Cite this