Matching nuts and bolts faster. (English) Zbl 0875.68545
Summary: 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 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 explicit deterministic algorithm to date is due to Alon et al. (1994) and takes \(\Theta(n\log^4 n)\) time. We give a simpler \(\text{O}(n\log^2 n)\) time algorithm. The existence of an \(\text{O}(n\log n)\) time algorithm has been proved recently (Bradford, 1995; Komlós et al., 1996).
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
References:
| [1] | Ajtai, M.; Komlós, J.; Szemerédy, E., An \(O(n\) log \(n)\) sorting network, (Proc. 15th ACM Symp. on the Theory of Computing (STOC’83) (1983)), 1-9 |
| [2] | Alon, N.; Blum, M.; Fiat, A.; Kannan, S.; Naor, M.; Ostrovsky, R., Matching nuts and bolts, (Proc. 5th Ann. ACMSIAM Symp. on Discrete Algorithms (SODA’94) (1994)), 690-696 · Zbl 0871.68100 |
| [3] | Alon, N.; Galil, Z.; Milman, V. D., Better expanders and superconcentrators, J. Algorithms, 8, 337-347 (1987) · Zbl 0641.68102 |
| [4] | Alon, N.; Spencer, J., The Probabilistic Method (1992), Wiley: Wiley New York · Zbl 0767.05001 |
| [5] | Bradford, P. G.; Fleischer, R., Matching nuts and bolts faster, (Proc. 6th Internat. Symp. on Algorithms and Computation (ISAAC’95) (1995)), 402-408 · Zbl 0875.68545 |
| [6] | Bradford, P. G., Matching nuts and bolts optimally, (Tech. Rept. MPI-I-95-1-025 (1995), Max-Planck-Institut für Informatik: Max-Planck-Institut für Informatik Saarbrücken, Germany) · Zbl 0875.68545 |
| [7] | Cormen, T. H.; Leiserson, C. E.; Rivest, R. L., Introduction to Algorithms (1990), MIT Press: MIT Press Cambridge, MA · Zbl 1158.68538 |
| [8] | Goddard, W.; Kenyon, C.; King, V.; Schulman, L., Optimal randomized algorithms for local sorting and set-maxima, SIAM J. Comput., 22, 272-283 (1993) · Zbl 0770.68047 |
| [9] | Komlós, J.; Ma, Y.; Szemerédi, E., Matching nuts and bolts in \(O(n\) log \(n)\) time, (Proc. 7th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’96) (1996)), 232-241 · Zbl 0852.68018 |
| [10] | Lubotzky, A., Discrete Groups, Expanding Graphs and Invariant Measures (1994), Birkhäuser: Birkhäuser Basel · Zbl 0826.22012 |
| [11] | Lubotzky, A.; Phillips, R.; Sarnak, P., Explicit expanders and the Ramanujan conjectures, (Proc. 18th ACM Symp. on the Theory of Computing (STOC’86) (1986)), 240-246 |
| [12] | Lubotzky, A.; Phillips, R.; Sarnak, P., Ramanujan graphs, Combinatorica, 8, 261-277 (1988) · Zbl 0661.05035 |
| [13] | Margulis, G. A., Problems of Information Transmission, 24, 39-46 (1988), English translation in: · Zbl 0708.05030 |
| [14] | Munro, J. I.; Paterson, M., Selection and sorting with limited storage, Theoret. Comput. Sci., 12, 315-323 (1980) · Zbl 0441.68067 |
| [15] | Rawlins, G. J.E., Compared to What? An Introduction to the Analysis of Algorithms (1992), Computer Science Press: Computer Science Press Rockville, MD · Zbl 0824.68044 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
