An efficient algorithm for row minima computations in monotone matrices
説明
A matrix A of size m/spl times/n containing items from a totally ordered universe is termed monotone if for every i, j, 1/spl les/i 2. Our second contribution is to exhibit a number of non-trivial lower bounds for matrix search problems. These lower bound results hold for arbitrary infinite two-dimensional reconfigurable meshes as long as the input is pretiled onto an n/spl times/n submesh thereof. Specifically, in this context we show that every algorithm that solves the problem of computing the minimum of an n/spl times/n matrix must take /spl Omega/(log log n) time. The same lower bound is shown to hold for the problem of computing the minima in each row of all arbitrary n/spl times/n matrix. As a by product we obtain an /spl Omega/(log log n) time lower bound for the problem of selecting the k-th smallest item in a monotone matrix, thus extending the previously best known lower bound for selection of the reconfigurable mesh. Finally, we show an almost tight /spl Omega/(/spl radic/(log log n)) time lower bound for the task of computing the row minima of a monotone n/spl times/n matrix.
収録刊行物
-
- Proceedings of the 1996 ICPP Workshop on Challenges for Parallel Processing
-
Proceedings of the 1996 ICPP Workshop on Challenges for Parallel Processing 2 54-61, 2002-12-24
IEEE Comput. Soc. Press