|
Abstract |
A natural optimization model that formulates many online resource allocation and data-driven management problems is the online linear program (LP) where the constraint matrix is revealed column by column along with the objective function. We provide a near-optimal algorithm for this surprisingly general class of online problems under the assumption of random order of arrival and some mild conditions on the size of the LP right-hand-side input. Our algorithm has a feature of "learning while doing" by dynamically updating a threshold price vector at geometric time intervals, where the dual prices learned from revealed columns in the previous period are used to determine the sequential decisions in the current period. In particular, our algorithm doesn't assume any distribution information on the input itself, thus is robust to data uncertainty and variations due to its dynamic learning capability. Joint work with Shipra Agrawal and Zizhuo Wang. |
