Skip to main content.
Advanced search >
<< Back to previous page Print

<< Monday, October 15, 2012 >>


Remind me

Tell a friend

Add to my Google calendar (bCal)

Download to my calendar

Bookmark and ShareShare


Recent Progresses on Linear Programming and the Simplex Method

Seminar: Departmental | October 15 | 2:30-3:30 p.m. | 521 Cory Hall


Prof Yinyu Ye, Professor, Stanford University

Qualcomm Inc


Linear programming (LP), together with the simplex method, remain a core topic in Operations Research, Computer Science and Mathematics 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 constant discount factors, the strongly polynomial-time complexity of the simplex method for solving deterministic MDP regardless discounts, etc.


venkyne@eecs.berkeley.edu