Notice: eScholarship will undergo scheduled maintenance from Tuesday, January 21 to Wednesday, January 22. Some functionality may not be available during this time. Learn more at eScholarship Support.
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
Main Content
For improved accessibility of PDF content, download the file to your device.
