×

On searching strategies, parallel questions, and delayed answers. (English) Zbl 1062.68046

Summary: We study the effect that delayed answers can have on binary search procedures.

MSC:

68P10 Searching and sorting
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aigner, M., Combinatorial Search (1988), Wiley-Teubner: Wiley-Teubner New York-Stuttgart · Zbl 0663.68076
[2] S. Albers, M. Charikar, M. Mitzenmacher, Delayed information and action in on-line algorithms, in: Proceedings of 39th FOCS, 1998, pp. 71-81.; S. Albers, M. Charikar, M. Mitzenmacher, Delayed information and action in on-line algorithms, in: Proceedings of 39th FOCS, 1998, pp. 71-81. · Zbl 1005.68070
[3] Ambainis, A.; Bloch, S. A.; Schweizer, D. L., Delayed binary search, or playing twenty questions with a procrastinator, Algorithmica, 32, 641-651 (2002) · Zbl 0992.68040
[4] Bar-Noy, A.; Kipnis, S., Designing broadcast algorithms in the postal model for message-passing systems, Math. Systems Theory, 27, 431-452 (1994) · Zbl 0812.68079
[5] Bar-Noy, A.; Kipnis, S.; Shieber, B., An optimal algorithm for computing census functions in message-passing systems, Parallel Process. Lett, 3, 1, 19-23 (1993)
[6] F. Cicalese, U. Vaccaro, Coping with delays and time-outs in binary search procedures, in: 11th Annual Internat. Symposium on Algorithms and Computation (ISAAC2000), Lecture Notes in Computer Science, Vol. 1969, Springer, Berlin, 2000, pp. 96-107.; F. Cicalese, U. Vaccaro, Coping with delays and time-outs in binary search procedures, in: 11th Annual Internat. Symposium on Algorithms and Computation (ISAAC2000), Lecture Notes in Computer Science, Vol. 1969, Springer, Berlin, 2000, pp. 96-107. · Zbl 1044.68745
[7] D. Culler, R. Karp, D. Patterson, A. Sahay, K.E. Schauser, E. Santos, R. Subramonian, T. von Eicken, LogP: toward a realistic model of parallel computation, ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, 1993, pp. 1-12.; D. Culler, R. Karp, D. Patterson, A. Sahay, K.E. Schauser, E. Santos, R. Subramonian, T. von Eicken, LogP: toward a realistic model of parallel computation, ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, 1993, pp. 1-12.
[8] Du, D. Z.; Hwang, F. K., Combinatorial Group Testing and its Applications (1993), World Scientific: World Scientific Singapore · Zbl 0784.90046
[9] Golin, M.; Schuster, A., Optimal point-to-point broadcast algorithms via lopsided trees, Discrete Appl. Math, 93, 233-263 (1999) · Zbl 1031.90006
[10] Kung, H. T., Synchronized and asynchronous parallel algorithms for multiprocessors, (Traub, J. F., Algorithms and Complexity: New Directions and Recent Results (1979), Academic Press: Academic Press NY), 153-200 · Zbl 0368.68039
[11] Pelc, A., Searching games with errors-fifty years of coping with liars, Theoret. Comput. Sci, 243, 1,2, 71-109 (2002) · Zbl 0984.68041
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.