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

MPI-I-95-1-025

Matching nuts and bolts optimally

Bradford, Phillip G.

MPI-I-95-1-025. October 1995, 24 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
The nuts and bolts problem is the following :
Given a collection of $n$ nuts of distinct sizes and $n$ bolts of distinct
sizes such that for each nut there is exactly one matching bolt,
find for each nut its corresponding bolt subject
to the restriction that 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 quite difficult to solve.
In this paper, we illustrate the existence of an algorithm
for solving the nuts and bolts problem that makes
$O(n \lg n)$ nut-and-bolt comparisons.
We show the existence of this algorithm by showing
the existence of certain expander-based comparator networks.
Our algorithm is asymptotically optimal in terms of the number
of nut-and-bolt comparisons it does.
Another view of this result is that we show the existence of a
decision tree with depth $O(n \lg n)$ that solves this problem.
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-025.pdfMPI-I-95-1-025.pdfMPI-I-95-1-025.dvi.gz45 KBytes; 166 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-025
Hide details for BibTeXBibTeX
@TECHREPORT{Bradford95,
  AUTHOR = {Bradford, Phillip G.},
  TITLE = {Matching nuts and bolts optimally},
  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-025},
  MONTH = {October},
  YEAR = {1995},
  ISSN = {0946-011X},
}