# Item

ITEM ACTIONSEXPORT

Released

Report

#### Matching nuts and bolts faster

##### MPS-Authors

##### Locator

There are no locators available

##### Fulltext (public)

MPI-I-95-1-003.pdf

(Any fulltext), 143KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Bradford, P. G., & Fleischer, R.(1995). *Matching nuts and
bolts faster* (MPI-I-1995-1-003). Saarbrücken: Max-Planck-Institut für Informatik.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-A846-5

##### 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 {\em 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 to date is due
to Alon {\it et al\/.} [1] and takes $\Theta(n \log^4 n)$
time. Their solution uses (efficient) graph expanders. In this paper,
we give a simpler $\Theta(n \log^2 n)$ time algorithm which uses only
a simple (and not so efficient) expander.