Norman and Lotfi Zadeh Prize Announced


Warning: If you do not understand the following, you will not be alone.

Approximately thirty years ago, Norm Zada (then “Zadeh”) offered $1,000 to anyone who could create examples of linear programming problems that would take an exponential number of steps to solve using the Simplex Method, employing a rule he created for selecting the next incoming variable. (See link below). (In Linear programming, the trick is to find the right combination of variables that provides the maximum objective function value while at the same time satisfying a system of linear equations. The Simplex Method, which was created by George Dantzig, begins with an initial feasible solution, and then progressively moves to better and better solutions by changing the combination of selected variables, until the maximum objective function value is obtained.) This all came about because to get his Ph.D. from U.C. Berkeley, Norm created a sequence of pathological linear programming network flow problems which took an exponential number of steps using the Simplex Method, to reach the optimal solution. Norm created those examples in the following way. Once he created a pathological problem with N variables which took 2**N iterations to solve, to get the pathological example with N+1 variables which took 2**(N+1) iterations, Norm made sure that the N+1th variable was so expensive that it would not be used until the first N variables were used to the maximum extent possible. When the N+1th variable was finally used, the sequence of iterations using that variable exactly reversed the prior set of 2**N iterations. In other words, if the iteration sequence for a pathological example with N variables was 1—›2**N, the iteration sequence for the pathological example with N+1 variables was 1—›2**N followed by the addition of the N+1th variable, followed by essentially the reverse iteration sequence 2**N—› 1, except that the N+1th variable was now part of the selected set of variables. Norm realized that a rule which required the improving variable which had been used least to be used next, would destroy the method he used to generate the sequence of pathological examples, which compelled him to make the $1,000 offer.

Thirty years later, Norm got a call that Oliver Friedmann, from Germany, had solved his problem.

This led a celebration at the Institute of Pure and Applied Mathematics at UCLA, where Norm was forced to write Oliver a check. While having lunch with some of the illustrious seminar attendees, it became clear to Norm that more prize money was needed to reward those brilliant solvers of unsolved mathematical problems. So Norm decided to set up a modest prize pool to reward such excellence. The prizes will be awarded under the name the “Norman and Lotfi Zadeh Prize.” Norm’s father, Lotfi, created Fuzzy Logic.

http://gilkalai.wordpress.com/2011/01/20/gunter-ziegler-1000-from-beverly-hills-for-a-math-problem-ipam-remote-blogging/#more-5966

Feb 22, 2011

P10® Copyright © Perfect 10®, Inc. 1996-2017 18 U.S.C. 2257 Record-Keeping Requirements Compliance Statement

Perfect 10's DMCA Agent, for receiving notifications of claims of copyright infringement or other intellectual property infringement, can be reached as follows:

Perfect 10, Inc., Attn: COPYRIGHT AGENT
11803 Norfield Court, Los Angeles, CA 90077
Telephone: (310) 476-0700, Facsimile: (310) 476-8138, e-mail: melanie@perfect10.com

Share |