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.
Print
Remind me
Add to my Google calendar (bCal)
Share