article · Operations Research · 2014

A Dynamic Near-Optimal Algorithm for Online Linear Programming

Cited by 253Abstract and details only

Abstract

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.

Cite this paper

APA 7

Agrawal, S., Wang, Z., & Ye, Y. (2014). A Dynamic Near-Optimal Algorithm for Online Linear Programming. Operations Research, 62(4), 876–890. https://doi.org/10.1287/opre.2014.1289

MLA 9

Agrawal, Shipra, et al. “A Dynamic Near-Optimal Algorithm for Online Linear Programming.” Operations Research, vol. 62, no. 4, 2014, pp. 876–90, https://doi.org/10.1287/opre.2014.1289.

Chicago

Agrawal, Shipra, Zizhuo Wang, and Yinyu Ye. 2014. “A Dynamic Near-Optimal Algorithm for Online Linear Programming.” Operations Research 62 (4): 876–90. https://doi.org/10.1287/opre.2014.1289.

Harvard

Agrawal, S., Wang, Z. and Ye, Y. (2014) ‘A Dynamic Near-Optimal Algorithm for Online Linear Programming’, Operations Research, 62(4), pp. 876–890. Available at: https://doi.org/10.1287/opre.2014.1289.

BibTeX

@article{agrawal2014dynamic,
  title = {{A Dynamic Near-Optimal Algorithm for Online Linear Programming}},
  author = {Agrawal, Shipra and Wang, Zizhuo and Ye, Yinyu},
  journal = {Operations Research},
  volume = {62},
  number = {4},
  pages = {876--890},
  year = {2014},
  doi = {10.1287/opre.2014.1289}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.