Matching Nuts and Bolts

TitleMatching Nuts and Bolts
Publication TypeTechnical Report
Year of Publication1993
AuthorsAlon, N., Blum M. E., Fiat A., Kannan S., Naor M., & Ostrovsky R.
Other Numbers863

We describe a procedure which may be helpful to any disorganized carpenter who has a mixed pile of bolts and nuts and wants to find the corresponding pairs of bolts and nuts. The procedure uses our (and the carpenter's) ability to construct efficiently highly expanding graphs. The problem considered is given a collection of n bolts of distinct widths and n nuts such that there is a 1-1 correspondence between the nuts and bolts. The goal is to find for each bolt its corresponding nut by comparing nuts to bolts but not nuts to nuts or bolts to bolts. Our objective is to minimize the number of operations of this kind (as well as the total running time). The problem has a randomized algorithm similar to Quicksort. Our main result is an n (log n)^{O(1)}-time deterministic algorithm, based on expander graphs, for matching the bolts and the nuts.

Bibliographic Notes

ICSI Technical Report TR-93-075

Abbreviated Authors

N. Alon, M. Blum, A. Fiat, S. Kannan, M. Naor, and R. Ostrovsky

ICSI Publication Type

Technical Report