Karl-Heinz Borgwardt

Karl-Heinz Borgwardt received the prize for his two articles, "Some Distribution-lndependent Results About the Asymptotic Order of the Average Number of Pivot Steps of the Simplex-Method," Mathematics of Operations Research 7:3 (August 1982), pp. 441-462, and "The Average Number of Pivot Steps Required by the Simplex-Method is Polynomial," Zeitschrift fur Operations Research Series A: Theory 26:5 (September 1982), pp. 157-177.

The Committee's citation is as follows:

• "Until recently there were three major open problems in the field of linear programming:
  • (1) Are linear programming problems solvable in polynomial time?
  • (2) Is there a polynomial time version of the simplex method?
  • (3) How can the extremely good practically observed performance of the simplex method be explained?
• "Problem (1) has been solved in a theoretical sense with the invention of the ellipsoid method. This approach provides a polynomial algorithm for linear programming which behaves very poorly in practice. However, it answered a question that had been bothering a large number of prominent scientists for about thirty years. The contributors to the ellipsoid method received the 1982 Fulkerson Prize for their results.
• "Problem (2) is still open. It may happen, as in the case of the ellipsoid method, that if a provably polynomial time version of the simplex method is found, it will show bad practical behavior. This, a positive answer to (2), would not necessarily solve (3).
• "Problem (3) has been solved by Karl-Heinz Borgwardt in the papers cited above. Dr. Borgwardt shows that the average running time of a version of the simplex method is bounded by a polynomial in n (the number of variables) and m (the number of rows), i.e., that whenever we take an LP problem we may expect a good performance of the simplex method. Dr. Borgwardt's analysis shows that the examples of Klee & Minty type which force various variants of the simplex method to perform an exponential number of pivot steps are extremely rare.
• "Solving an extremely important theoretical question that has defied researchers for decades is always an outstanding contribution to science. But here in addition the analysis is deep, clever and competent, and some beautiful ideas combining results from various areas of mathematics are developed which finally give the desired result. An interesting new version of the simplex method (Schatteneckenalgorithmus) is even designed.
• "This work is not the last word to be said on the subject; indeed, there is currently a great deal of activity in the field. It is the opinion of this Committee, shared by many experts on the subject, that Dr. Borgwardt's results constitute a pioneering breakthrough which has excited and motivated others to work on this fundamental problem, and we have therefore selected him to receive the Prize."