Scientific Program

Semi-plenary Lecture

Program -> Plenary and Semi-Plenary -> Tue.9:00.H 0105 title only | abstract | bio sketch

Tuesday, 9:00 - 9:50 h, H 0105


Yinyu Ye
Tseng Memorial Lecture - Recent Progresses in Linear Programming and the Simplex Method


Chair: Sven Leyffer


Abstract:
We prove that the classic policy-iteration method (Howard 1960), including the Simplex method (Dantzig 1947) with the most-negative-reduced-cost pivoting rule, is a strongly polynomial-time algorithm for solving the Markov decision process (MDP) with a constant discount factor. Furthermore, the computational complexity of the policy-iteration method (including the Simplex method) is superior to that of the only known strongly polynomial-time interior-point algorithm for solving this problem, which seems consistent with practical observation. The result is surprising since the Simplex method with the same pivoting rule was shown to be exponential for solving a general linear programming (LP) problem, the Simplex method with the smallest-index pivoting rule was shown to be exponential for solving an MDP regardless of discount rates, and the policy-iteration method was recently shown to be exponential for solving a undiscounted MDP. We also describe most recent progresses in this research direction.the Tseng Memorial Lectureship. The prize was established in 2011 and will be awarded for the first time during the opening ceremony of ISMP 2012.

 

Biographical sketch:
Yinyu Ye is currently a Professor of Management Science and Engineering and Institute of Computational and Mathematical Engineering and the Director of the MS&E Industrial Affiliates Program, Stanford University. He received the B.S. degree in System Engineering from the Huazhong University of Science and Technology, China, and the M.S. and Ph.D. degrees in Engineering-Economic Systems and Operations Research from Stanford University. His current research interests include Continuous and Discrete Optimization, Algorithm Design and Analysis, Computational Game/Market Equilibrium, Metric Distance Geometry, Dynamic Resource Allocation, and Stochastic and Robust Decision Making, etc. He is an INFORMS (The Institute for Operations Research and The Management Science) Fellow, and has received several research awards including the 2009 John von Neumann Theory Prize for fundamental sustained contributions to theory in Operations Research and the Management Sciences, the inaugural 2006 Farkas prize on Optimization, and the 2009 IBM Faculty Award. He has supervised numerous doctoral students who received the 2008 Nicholson Prize and the 2006 and 2010 INFORMS Optimization Prizes for Young Researchers.

 

 

Program -> Plenary and Semi-Plenary -> Tue.9:00.H 0105 title only | abstract | bio sketch

  In particular, Texas Loans Online can cater to the needs of its residents. Moreover, to order Cialis Daily online is highly advantageous because it interacts well with the small portions of alcohol and food.