# The ICICS/CS Reading Room

## UBC CS TR-90-26 Summary

- No on-line copy of this technical report is available.

- Superlinear Bounds for Matrix Searching Problems, July 1990 Maria M. Klawe
Matrix searching in classes of totally monotone partial matrices has many applications in computer science,
operations research, and other areas. This paper gives the first superlinear bound for matrix searching in
classes of totally monotone partial matrices, and also contains some new upper bounds for a class with
applications in computational geometry and dynamic programming.
\n The precise results of this paper are as follows. We show that any algorithm for finding row maxima or
minima in totally monotone partial $2n \times n$ matrices with the property that the non-blank entries in each
column form a contiguous segment, can be forced to evaluate $\Omega (n \alpha (n))$ entries of the matrix in order to find
the row maxima or minima, where $\alpha (n)$ denotes the very slowly growing inverse of Ackermann's function.
A similar result is obtained for $n \times 2n$ matrices with contiguous non-blank segments in each row. The lower
bounds are proved by introducing the concept of an independence set in a partial matrix and showing that
any matrix searching algorithm for these types of partial matrices can be forced to evaluate every element
in the independence set. A result involving lower bounds for Davenport-Schinzel sequences is then used to
construct an independence set of size $\Omega (n \alpha (n))$ in the matrices of size $2n \times n$ and $n \times 2n$.
\n We also give two algorithms to find row maxima and minima in totally monotone partial $n \times m$ matrices
with the property that the non-blank entries in each column form a contiguous segment ending at the bottom
row. The first algorithm evaluates at most $O (m \alpha (n) + n)$ entries of the skyline matrix and performs at most
that many comparisons, but may have $O (m \alpha (n) \log \log n+ n)$ total running time. The second algorithm is
simpler and has $O (m \log \log n+ n)$ total running time.
\n A preliminary version of this paper appeared in the Proceedings of the First ACM/SIAM Symposium
on Discrete Algorithms, 1990. The research in this paper was partially supported by an NSERC Operating
Grant.

If you have any questions or comments regarding this page please send mail to
help@cs.ubc.ca.