Matching nuts and bolts

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

Matching nuts and bolts

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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 language	English (US)
Title of host publication	Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms
Publisher	Publ by ACM
Pages	690-696
Number of pages	7
ISBN (Print)	0898713293
State	Published - 1994
Externally published	Yes
Event	Proceedings of the Fifth Annual SIAM Symposium on Discrete Algorithms - Arlington, VA, USA Duration: Jan 23 1994 → Jan 25 1994

Publication series

Name	Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms

Other

Other	Proceedings of the Fifth Annual SIAM Symposium on Discrete Algorithms
City	Arlington, VA, USA
Period	1/23/94 → 1/25/94

All Science Journal Classification (ASJC) codes

Software
General Mathematics

Cite this

@inproceedings{1fe23f97a8524e8c8f34778185b9e4f6,

title = "Matching nuts and bolts",

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.",

author = "Noga Alon and Manuel Blum and Amos Fiat and Sampath Kannan and Moni Naor and Rafail Ostrovsky",

year = "1994",

language = "English (US)",

isbn = "0898713293",

series = "Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms",

publisher = "Publ by ACM",

pages = "690--696",

booktitle = "Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms",

note = "Proceedings of the Fifth Annual SIAM Symposium on Discrete Algorithms ; Conference date: 23-01-1994 Through 25-01-1994",

}

TY - GEN

T1 - Matching nuts and bolts

AU - Alon, Noga

AU - Blum, Manuel

AU - Fiat, Amos

AU - Kannan, Sampath

AU - Naor, Moni

AU - Ostrovsky, Rafail

PY - 1994

Y1 - 1994

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0028263308&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0028263308&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0028263308

SN - 0898713293

T3 - Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms

SP - 690

EP - 696

BT - Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms

PB - Publ by ACM

T2 - Proceedings of the Fifth Annual SIAM Symposium on Discrete Algorithms

Y2 - 23 January 1994 through 25 January 1994

ER -

Matching nuts and bolts

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this