Matching nuts and bolts in O(n log n) time

作     者：Komlos, J Ma, Y Szemeredi, E 

作者机构：Rutgers State Univ Dept Math Piscataway NJ 08855 USA Stanford Univ Dept Comp Sci Stanford CA 94305 USA MIT Cambridge MA 02139 USA Rutgers State Univ Dept Comp Sci Piscataway NJ 08855 USA Univ Gesamthsch Paderborn D-4790 Paderborn Germany 

出 版 物：《SIAM JOURNAL ON DISCRETE MATHEMATICS》 (工业与应用数学会离散数学杂志)

年 卷 期：1998年第11卷第3期

页      面：347-372页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

主　　题：sorting matching selection parallel computation AKS sorting algorithm random graphs 

摘      要：Given a set of n nuts of distinct widths and a set of n bolts such that each nut corresponds to a unique bolt of the same width, how should we match every nut with its corresponding bolt by comparing nuts with bolts? (No comparison is allowed between two nuts or two bolts.) The problem can be naturally viewed as a variant of the classic sorting problem as follows. Given two lists of n numbers each such that one list is a permutation of the other, how should we sort the lists by comparisons only between numbers in different lists? We give an O(n log n)-time deterministic algorithm for the problem. This is optimal up to a constant factor and answers an open question posed by Alon et al. [Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms, 1994, pp. 690-696]. Moreover, when copies of nuts and bolts are allowed, our algorithm runs in optimal O(log n) time on n processors in Valiant s parallel comparison tree model. Our algorithm is based on the AKS sorting algorithm with substantial modifications.