de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Report

Matching nuts and bolts faster

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44170

Bradford,  Phillip Gnassi
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44431

Fleischer,  Rudolf
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

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.