Matching nuts and bolts

Noga Mordechai Alon, Manuel Blum, Amos Fiat, Sampath Kannan, Moni Naor, Rafail Ostrovsky

Research output: Chapter in Book/Report/Conference proceedingConference contribution

13 Scopus citations

Abstract

We describe a procedure which may be helpful to any disorganized carpenter who has a mixed pile of bolts and nuts and wants to find the corresponding pairs of bolts and nuts. The procedure uses our (and the carpenter's) ability to construct efficiently highly expanding graphs. The problem considered is given a collection of n bolts of distinct widths and n nuts such that there is a 1-1 correspondence between the nuts and bolts. The goal is to find for each bolt its corresponding nut by comparing nuts to bolts but not nuts to nuts or bolts to bolts. Our objective is to minimize the number of operations of this kind (as well as the total running time). The problem has a randomized algorithm similar to Quicksort. Our main result is an n(log n)O(1)-time deterministic algorithm, based on expander graphs, for matching the bolts and the nuts.

Original languageEnglish (US)
Title of host publicationProceedings of the Annual ACM SIAM Symposium on Discrete Algorithms
PublisherPubl by ACM
Pages690-696
Number of pages7
ISBN (Print)0898713293
StatePublished - Jan 1 1994
Externally publishedYes
EventProceedings of the Fifth Annual SIAM Symposium on Discrete Algorithms - Arlington, VA, USA
Duration: Jan 23 1994Jan 25 1994

Other

OtherProceedings of the Fifth Annual SIAM Symposium on Discrete Algorithms
CityArlington, VA, USA
Period1/23/941/25/94

All Science Journal Classification (ASJC) codes

  • Chemical Health and Safety
  • Software
  • Safety, Risk, Reliability and Quality
  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'Matching nuts and bolts'. Together they form a unique fingerprint.

  • Cite this

    Alon, N. M., Blum, M., Fiat, A., Kannan, S., Naor, M., & Ostrovsky, R. (1994). Matching nuts and bolts. In Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms (pp. 690-696). Publ by ACM.