Rafail Ostrovsky - Publications

Matching Nuts and Bolts.

Noga Alon, Manuel Blum, Amos Fiat, Sampath K. Kannan, Moni Naor, Rafail Ostrovsky

Abstract: We describe a procedure which may be helpful to any disorganized carpenter having a mixed pile of bolts and nuts together with the 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 one-to-one 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 Quick-sort. Our main result is an n (log n)O(1)-time deterministic algorithm for matching the bolts and the nuts. The algorithm applies expander graphs in an interesting way, and its proof of correctness requires several rather subtle arguments.

comment: Appeared In Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-94)

Fetch PostScript file of the paper     Fetch PDF file of the paper

Back to Publications List