2014-05-16

Prof. YE Yinyu gave a lecture named “A Dynamic Near-Optimal Algorithm for Online Linear Programming” on May 13, 2014.

In his lecture, he and his co-authors provided 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. Their 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, the 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.

Prof. YE Yinyu is a professor from Department of Management Science and Engineering (MS&E), Stanford University. He is also the Director of Industrial Affiliates Program, MS&E. His research interests are mathematical programming, optimization algorithm design and analysis, computational complexity and operations research and its applications.