Video Excerpt

IRV
How did your work in linear programming influence you in other areas?

One had to do with an estimation of eigenvalues on matrices. In my work with Helmut Wielandt, a visiting mathematician from Germany, we studied the question of eigenvalues as related to matrices and distances, and we solved it using linear programming. Our theorem on the estimation of eigenvalues is called the Hoffman-Wielandt theorem. It was a thrill to me to see that linear programming could be applied to other parts of mathematics, including combinatorial problems, like the Konig-Egervary theorem. It was through this theorem, rather than through the diet problem, that I was able to understand duality.

IRV
George mentioned the diet problem in my interview with him as one of the first problems ever solved. Were there others?

ALAN
Yes, and they were solved using hand computers! Here's the diet problem. It goes like this: you have a drug manufacturer who wants to sell pills that correspond to the nutrients needed for the cheapest, yet most nutritiously efficient, diet. The question is how should these pills be priced so that the manufacturer makes money and that people buying them don't feel they're paying more for the pills than they would for the corresponding food? I couldn't develop an intuition for the duality theorem by thinking about pricing the pills, but my work on the linear programming proof of the Konig-Egervary theorem developed that intuition. And I thought, "My goodness, I can do a lot of combinatorial things using linear programming," which in fact I proceeded to do.

Previous

Next