Location: Rm 1114, Science Building #1

Time: 3-4pm, Tuesday Sep 11（9月11日，星期二，15：00---16：00）

Speaker: Yinyu Ye, Stanford University

Abstract: Linear programming (LP), together with the simplex method, remain a core Operations Research, Computer Science and Mathematics topic since 1947. Due to the relentless research effort, a linear program can be solved today one million times faster than it was done thirty years ago. Businesses, large and small, now use LP models to control manufacture inventories, price commodities, design civil/communication networks, and plan investments. LP even becomes a popular subject taught in under/graduate and MBA curriculums, advancing human knowledge and promoting science education. The aim of the talk is to describe several recent exciting progresses on LP and the simplex method, include counter examples to the Hirsch conjecture, some pivoting rules and their exponential behavior, strongly polynomial-time bounds of the simplex and policy-iteration methods for solving Markov decision process (MDP) and turn-based zero-sum game with any constant discount factor, the strongly polynomial-time complexity of the simplex method for solving deterministic MDP regardless discounts, etc.

Short Bio:
Yinyu Ye is currently a full 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 inaugural 2012 ISMP Tseng Lectureship Prize for outstanding contribution to continuous optimization, 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 at Stanford who received the 2008 Nicholson Prize and the 2006 and 2010 INFORMS Optimization Prizes for Young Researchers.