A Dynamic Near-Optimal Algorithm for Online Linear Programming

Event Details
  • Date/Time:
    • Tuesday February 23, 2010 - Wednesday February 24, 2010
      10:00 am - 10:59 am
  • Location: ISyE Executive classroom
  • Phone:
  • URL:
  • Email:
  • Fee(s):
  • Extras:
No contact information submitted.

Summary Sentence: A Dynamic Near-Optimal Algorithm for Online Linear Programming

Full Summary: A Dynamic Near-Optimal Algorithm for Online Linear Programming

TITLE: A Dynamic Near-Optimal Algorithm for Online Linear Programming

SPEAKER: Professor Yinyu Ye


A natural optimization model that formulates many online resource allocation and revenue
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 learning-based algorithm works 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. Our algorithm has a feature of learning by doing, and the prices are updated at a carefully chosen pace that is neither too fast nor too slow. 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. Applications of our algorithm include many online multi-resource allocation and multi-product revenue management problems such as online routing and packing, online combinatorial auctions, adwords matching, inventory control and yield management.

Joint work with Shipra Agrawal and Zizhuo Wang.

Additional Information

In Campus Calendar

School of Industrial and Systems Engineering (ISYE)

Invited Audience
No audiences were selected.
No keywords were submitted.
  • Created By: Anita Race
  • Workflow Status: Published
  • Created On: Jan 20, 2010 - 5:00am
  • Last Updated: Oct 7, 2016 - 9:49pm