Minimax Programs

We introduce an optimization problem called a minimax program that is similar to a linear program, except that the addition operator is replaced in the constraint equations by the maximum operator. We clarify the relation of this problem to some better-known problems. We identify an interesting special case and present an efficient algorithm for its solution. 1 Introduction Over the last fifty years, thousands of problems of practical interest have been formulated as a linear program. Not only has the linear programming model proven to be widely applicable, but ongoing research has discovered highly effective algorithms for solution of various classes of linear programs. Linear programming represents one of the major achievements of the operations research and mathematical programming community. Supported in part by a National Science Foundation Graduate Fellowship. In this paper we introduce an optimization problem we call a "minimax program" that very much resembles a linear pr..