MPI-INF/SWS Research Reports 1991-2021

2. Number - All Departments


Matching nuts and bolts faster

Bradford, Phillip G. and Fleischer, Rudolf

May 1995, 7 pages.

Status: available - back from printing

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.

  • Attachement: (41 KBytes); MPI-I-95-1-003.pdf (142 KBytes)

URL to this document:

Hide details for BibTeXBibTeX
  AUTHOR = {Bradford, Phillip G. and Fleischer, Rudolf},
  TITLE = {Matching nuts and bolts faster},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-95-1-003},
  MONTH = {May},
  YEAR = {1995},
  ISSN = {0946-011X},