Premium
Minimax problems with bitonic matrices
Author(s) -
Hochbaum Dorit S.,
Tucker Paul A.
Publication year - 2002
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.10038
Subject(s) - minimax , combinatorics , cover (algebra) , column (typography) , set cover problem , generalization , mathematics , column generation , matrix (chemical analysis) , time complexity , scheduling (production processes) , set (abstract data type) , mathematical optimization , computer science , connection (principal bundle) , mechanical engineering , mathematical analysis , materials science , geometry , engineering , composite material , programming language
The minimax problem is a new optimization problem which substitutes maximum for addition in the constraint inequalities of a linear program. We show how a problem with n variables and m constraints can be reduced to a set cover problem with nm variables and m constraints. We define the mountain property on the coefficients in each column of the constraint matrix of a minimax problem and its generalization—the bitonic property. It is shown that these are equivalent, respectively, to set cover problems with consecutive 1's in each column or circular 1's in each column thus solving the periodic scheduling problem. We present a shortest path algorithm to solve a minimax problem with the mountain property in time O ( mn + log m ). For bitonic matrix problems, we present an algorithm of complexity O ( m 2 ( n + log n )). The same algorithms are used to solve a set cover problem on v sets and r elements to be covered in O ( v + r log r ) for a problem with consecutive 1's in each column and in O ( v ( v + r log r )) for a problem with circular 1's in each column. We further establish that r is at least \documentclass{article}\pagestyle{empty} \begin{document}$\Omega(\sqrt{v})$\end{document} and at most O ( v ). We also provide an efficient algorithm for recognizing bitonic matrices in O ( mn log m ) time. © 2002 Wiley Periodicals, Inc.