**
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 |