*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
TITLE: A Dynamic Near-Optimal Algorithm for Online Linear Programming
SPEAKER: Professor Yinyu Ye
ABSTRACT:
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.
