Abstract
The problem of matching nuts and bolts is the following: Given a collection of n nuts of distinct sizes and n bolts such that there is a one-to-one correspondence between the nuts and the bolts, find for each nut its corresponding bolt. We can only compare nuts to bolts. That is we can neither compare nuts to nuts, nor bolts to bolts. This humble restriction on the comparisons appears to make this problem very hard to solve. In fact, the best deterministic solution published to date is due to Alon et al. [2] and takes θ(n log4 n) time. Their solution uses (efficient) graph expanders. In this paper, we give a simpler O(n log2 n) time algorithm which uses only a simple (and not so efficient) expander.
The authors were supported by the ESPRIT Basic Research Actions Program, under contract No. 7141 (project ALCOM II).
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
N. Alon. Personal communication, 1995.
N. Alon, M. Blum, A. Fiat, S. Kannan, M. Naor and R. Ostrovsky. Matching nuts and bolts. Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'94), 1994, pp. 690–696.
N. Alon, Z. Galil and V.D. Milman. Better expanders and superconcentrators. Journal of Algorithms 8 (1987), pp. 337–347.
N. Alon and J. Spencer. The Probabilistic Method. John Wiley and Sons Inc., New York, 1992.
T.H. Cormen, C.E. Leiserson and R.L. Rivest. Introduction to algorithms. MIT Press, 1990.
W. Goddard, C. Kenyon, V. King and L. Schulman. Optimal randomized algorithms for local sorting and set-maxima. SIAM Journal on Computing 22, 1993, pp. 272–283.
J. Komlós, Y. Ma and E. Szemerédi. Matching nuts and bolts in O(n log n) time. Personal communication, Yuan Ma, 1995.
A. Lubotzky. Discrete groups, expanding graphs and invariant measures. Birkhäuser Verlag, 1994.
A. Lubotzky, R. Phillips and P. Sarnak. Explicit expanders and the Ramanujan conjectures. Proceedings of the 18th ACM STOC, 1986, pp. 240–246.
See also: A. Lubotzky, R. Phillips and P. Sarnak. Ramanujan graphs. Combinatorica 8 (1988), pp. 261–277.
G.A. Margulis. Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and superconcentrators. Problemy Peredachi Informatsii 24 (1988), pp. 51–60 (in Russian). English translation in Problems of Information Transmission 24 (1988), pp. 39–46.
J.I. Munro and M. Paterson. Selection and sorting with limited storage. Theoretical Computer Science 12, 1980, pp. 315–323.
G.J.E. Rawlins. Compared to what? An introduction to the analysis of algorithms. Computer Science Press, 1992.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bradford, P.G., Fleischer, R. (1995). Matching nuts and bolts faster. In: Staples, J., Eades, P., Katoh, N., Moffat, A. (eds) Algorithms and Computations. ISAAC 1995. Lecture Notes in Computer Science, vol 1004. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0015446
Download citation
DOI: https://doi.org/10.1007/BFb0015446
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60573-7
Online ISBN: 978-3-540-47766-2
eBook Packages: Springer Book Archive