A Dynamic Near-Optimal Algorithm for Online Linear Programming

By Shipra Agrawal, Zizhuo Wang, Yinyu Ye. Operational Research, 2009

341 citations recorded by the source corpus.

A natural optimization model that formulates many online resource allocation problems is the online linear programming LP problem in which the constraint matrix is revealed column by column along with the corresponding objective coefficient. In such a model, a decision variable has to be set each time a column is revealed without observing the future inputs, and the goal is to maximize the overall objective function. In this paper, we propose a near-optimal algorithm for this general class of online problems under the assumptions of random order of arrival and some mild conditions on the size of the LP right-hand-side input. Specifically, our learning-based algorithm works by dynamically updating a threshold price vector at geometric time intervals, where the dual prices learned from the revealed columns in the previous period are used to determine the sequential decisions in the current period. Through dynamic learning, the competitiveness of our algorithm improves over the past study of the same problem. We also present a worst case example showing that the performance of our algorithm is near optimal.

Subfields: Computer Networks and Communications, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/d79bd774308bf25b1c2b65a819c39b91fed60250

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Management Science and Operations Research

Citations in the corpus

Online Task Assignment in Crowdsourcing Markets (2012, methodology): “The online primal-dual framework can be used to achieve near-optimal performance on this problem when the total budget is sufﬁciently large (Agrawal, Wang, and Ye 2009; Feldman et al. 2010; Devanur et al. 2011).”
Online Matching and Ad Allocation (2013, methodology): “” Note that for a fixed distribution, the algorithm of [35] (and the generalizations in [6, 44]) provides precisely such a guarantee.”
Bandits with Knapsacks (2013, background): “…in recent years, starting with prior-free algorithms for the stochastic AdWords problem [25], and continuing with a series of papers extending these results from AdWords to more general stochastic packing integer programs while also achieving stronger performance guarantees [26], [27], [28], [29].”
Introduction to Multi-Armed Bandits (2019, background): “Third, estimating an optimal “dual” vector from samples and using this vector to guide subsequent “primal” decisions is a running theme in the work on stochastic packing problems (Devanur and Hayes, 2009; Agrawal et al., 2014; Devanur et al., 2019; Feldman et al., 2010; Molinaro and Ravi, 2012).”