Article ID: | iaor20164505 |
Volume: | 41 |
Issue: | 4 |
Start Page Number: | 1404 |
End Page Number: | 1431 |
Publication Date: | Nov 2016 |
Journal: | Mathematics of Operations Research |
Authors: | Gupta Anupam, Molinaro Marco |
Keywords: | programming: linear, heuristics, internet, matrices |
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 +