Zadeh's rule

In mathematical optimization, Zadeh's rule (also known as the least-entered rule) is an algorithmic refinement of the simplex method for linear optimization.

The rule was proposed around 1980 by Norman Zadeh (son of Lotfi A. Zadeh), and has entered the folklore of convex optimization since then.[1]

Zadeh offered a reward of $1,000 to anyone who can show that the rule admits polynomially many iterations or to prove that there is a family of linear programs on which the pivoting rule requires subexponentially many iterations to find the optimum.[2]

  1. ^ Zadeh, Norman (1980). "What is the worst case behaviour of the simplex algorithm?". Technical Report, Department of Operations Research, Stanford.
  2. ^ Ziegler, Günter (2004). "Typical and extremal linear programs". The Sharpest Cut (MPS-Siam Series on Optimization: 217–230. doi:10.1137/1.9780898718805.ch14. ISBN 978-0-89871-552-1.