Department of Computer Science & Engineering

This report describes an optimization problem called a minimax program that is similar to a linear program, except that the addition operator is replaced by the maximum operator in the constraint inequalities. The relation of this problem to some well-known problems is clarified. An interesting special case, bitonic columns, is identified, and a new, efficient algorithm is presented for its solution. Also presented is an efficient algortihm for recognition of matrices with the bitonic columns property, which is an extension of the PQ-tree reduction algorithm.

Pre-2018 CSE ID: CS1999-0624