Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-I-95-1-003

Matching nuts and bolts faster

Bradford, Phillip G. and Fleischer, Rudolf

MPI-I-95-1-003. May 1995, 7 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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.
Acknowledgement:
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-95-1-003.pdfMPI-I-95-1-003.pdfMPI-I-95-1-003.ps.gz41 KBytes; 142 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document: http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1995-1-003
Hide details for BibTeXBibTeX
@TECHREPORT{BradfordFleischer,
  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},
}