How experts can solve LPs online

Anupam Gupta, Marco Molinaro

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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: the main open question 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 constraint) to get (1+ε)-approximations online? It is known that the RHS has to be Ω(ε -2 logm) times the left-hand sides, where m is the number of constraints. In this paper we show how to achieve this bound for all packing LPs, and also for a wide class of 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 help 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)
Title of host publicationAlgorithms, ESA 2014 - 22nd Annual European Symposium, Proceedings
PublisherSpringer Verlag
Pages517-529
Number of pages13
ISBN (Print)9783662447765
DOIs
StatePublished - 2014
Event22nd Annual European Symposium on Algorithms, ESA 2014 - Wroclaw, Poland
Duration: Sep 8 2014Sep 10 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8737 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other22nd Annual European Symposium on Algorithms, ESA 2014
Country/TerritoryPoland
CityWroclaw
Period9/8/149/10/14

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

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

Cite this