TY - GEN

T1 - Comparison-sorting and selecting m totally monotone matrices

AU - Alon, Noga

AU - Azar, Yossi

N1 - Funding Information:
~artment of Mathematics, Raymond and Beverly Sacfder, Faculty of Exact Sciences, Tel Aviv University, Tel-Aviv, Israel, and Bellcore, Morristown, NJ, 07960, USA. Supported in part by a U. S. A.-Israeli BSF Grant and by a Bergmarm Memorial Grant tDEC Systems Research Center, 130 Lytton Ave. Palo-Alto, CA 94301. A portion of this work was done while the author was in the department of Computer Science, Stanford University, CA 94305-2140, and supported by a Weizmann fellowship and contract ONR NOO014-88-K-0166.

PY - 1992/9/1

Y1 - 1992/9/1

N2 - An m X n matrix A is called totally monotone if for all i1 < i2 and J1 < J2, A[i1, j1] > A[i2, J2] implies A[i2, J1] > A[i2, j2]. We consider the complexity of comparison-based selection and sorting algorithms in such matrices. Although our selection algorithm counts only comparisons its advantage on all previous work is that it can also handle selection of elements of different (and arbitrary) ranks in different rows (or even selection of elements of several ranks in each row), in time which is slightly better than that of the best known algorithm for selecting elements of the same rank in each row. We also determine the decision tree complexity of sorting each row of a totally monotone matrix up to a factor of at most log n by proving a quadratic lower bound and by slightly improving the upper bound. No nontrivial lower bound was previously known for this problem. In particular for the case m = n we prove a tight Ω(n2) lower bound. This bound holds for any decision-tree algorithm, and not only for a comparison-based algorithm. The lower bound is proved by an exact characterization of the bitonic totally monotone matrices, whereas our new algorithms depend on techniques from parallel comparison algorithms.

AB - An m X n matrix A is called totally monotone if for all i1 < i2 and J1 < J2, A[i1, j1] > A[i2, J2] implies A[i2, J1] > A[i2, j2]. We consider the complexity of comparison-based selection and sorting algorithms in such matrices. Although our selection algorithm counts only comparisons its advantage on all previous work is that it can also handle selection of elements of different (and arbitrary) ranks in different rows (or even selection of elements of several ranks in each row), in time which is slightly better than that of the best known algorithm for selecting elements of the same rank in each row. We also determine the decision tree complexity of sorting each row of a totally monotone matrix up to a factor of at most log n by proving a quadratic lower bound and by slightly improving the upper bound. No nontrivial lower bound was previously known for this problem. In particular for the case m = n we prove a tight Ω(n2) lower bound. This bound holds for any decision-tree algorithm, and not only for a comparison-based algorithm. The lower bound is proved by an exact characterization of the bitonic totally monotone matrices, whereas our new algorithms depend on techniques from parallel comparison algorithms.

UR - http://www.scopus.com/inward/record.url?scp=0347559801&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0347559801&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0347559801

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 403

EP - 408

BT - Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 1992

PB - Association for Computing Machinery

T2 - 3rd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 1992

Y2 - 27 January 1992 through 29 January 1992

ER -