English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
  Matching nuts and bolts optimally

Bradford, P. G.(1995). Matching nuts and bolts optimally (MPI-I-1995-1-025). Saarbrücken: Max-Planck-Institut für Informatik.

Item is

Files

show Files
hide Files
:
MPI-I-95-1-025.pdf (Any fulltext), 167KB
Name:
MPI-I-95-1-025.pdf
Description:
-
OA-Status:
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Bradford, Phillip G.1, Author
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, Campus E1 4, 66123 Saarbrücken, DE, ou_24019              

Content

show
hide
Free keywords: -
 Abstract: 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.

Details

show
hide
Language(s): eng - English
 Dates: 1995
 Publication Status: Issued
 Pages: 24 p.
 Publishing info: Saarbrücken : Max-Planck-Institut für Informatik
 Table of Contents: -
 Rev. Type: -
 Identifiers: URI: http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1995-1-025
Report Nr.: MPI-I-1995-1-025
BibTex Citekey: Bradford95
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: Research Report / Max-Planck-Institut für Informatik
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: - Identifier: -