Optimal parallel selection

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Optimal parallel selection

Full text

Pdf (926 KB)

Source

Symposium on Discrete Algorithms archive
Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms table of contents

Baltimore, Maryland

SESSION: Session 1A table of contents

Pages: 1 - 9

Year of Publication: 2003

ISBN:0-89871-538-5

Author

Yijie Han

University of Missouri at Kansas City, Kansas City, MO

Sponsors

: SIAM Activity Group on Discrete Mathematics
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics Philadelphia, PA, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 18, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

ABSTRACT

We present an optimal parallel selection algorithm on the EREW PRAM. This algorithm runs in O(log n) time with n/log n processors. This complexity matches the known lower bound for parallel selection on the EREW PRAM model. We therefore close this problem which has been open for more than a decade.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	M. Ajtai. Recursive construction for 3-regular expanders. Combinatorica, vol. 14, No. 4, 379--416(1994).
	2	Miklós Ajtai , János Komlós , W. L. Steiger , Endre Szemerédi, Optimal parallel selection had complexity O(log log N), Journal of Computer and System Sciences, v.38 n.1, p.125-133, February 1989 [doi>10.1016/0022-0000(89)90035-4]
	3	Y. Azar , N. Pippenger, Parallel selection, Discrete Applied Mathematics, v.27 n.1-2, p.49-58, May 1990 [doi>10.1016/0166-218X(90)90128-Y]
	4	M. Blum, R. W. Floyd, V. Pratt, R. L. Rivest, and R. E. Tarjan. Time bounds for selection. Journal of Computer and System Sciences, 7, (1973), pp. 448--461.
	5	Shiva Chaudhuri , Torben Hagerup , Rajeev Raman, Approximate and Exact Deterministic Parallel Selection, Proceedings of the 18th International Symposium on Mathematical Foundations of Computer Science, p.352-361, August 30-September 03, 1993
	6	K. W. Chong, Y. Han, Y. Igarashi, T. W. Lam. Improve parallel computation with fast integer sorting. Proceedings of the 5th International Conference on Computing and Combinatorics, Lecture Notes in Computer Sciecne 1627, 452--461(1999).
	7	Richard John Cole, An optimally efficient selection algorithm, Information Processing Letters, v.26 n.6, p.295-299, January 25, 1988 [doi>10.1016/0020-0190(88)90186-X]
	8	Stephen Cook , Cynthia Dwork , Ru&duml;ger Reischuk, Upper and lower time bounds for parallel random access machines without simultaneous writes, SIAM Journal on Computing, v.15 n.1, p.87-97, Feb. 1986 [doi>10.1137/0215006]
	9	Paul F. Dietz , Rajeev Raman, Small-rank selection in parallel, with applications to heap construction, Journal of Algorithms, v.30 n.1, p.33-51, Jan. 1999 [doi>10.1006/jagm.1998.0971]
	10	M. Fürer and B. Raghavachari. Parallel edge coloring approximation. Parallel Processing Letters6 (1996), 321--329.
	11	Y. Han, Matching partition a linked list and its optimization, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.246-253, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72961]
	12	Shuji Jimbo , Akira Maruoka, Expanders obtained from affine transformations, Combinatorica, v.7 n.4, p.343-355, Dec, 1987 [doi>10.1007/BF02579322]
	13	G. A. Magulis. Explicit construction of concentrators. Problemy Peredachi Informatsii, vol. 9, no. 4, 71--80(1973). (English translation in Problems of Inform. Transmission, 325--332(1975)).
	14	Sarnath Ramnath , Venkatesh Raman, Selecting small ranks in EREW PRAM, Information Processing Letters, v.71 n.5-6, p.183-186, Sept. 30, 1999 [doi>10.1016/S0020-0190(99)00113-1]
	15	R. Reischuk. Probabilistic parallel algorithms for sorting and selection. SIAM J. on Computing, 14 (1985), pp. 396--409.
	16	Hong Shen, Optimal parallel multiselection on EREW PRAM, Parallel Computing, v.23 n.13, p.1987-1992, Dec. 15, 1997 [doi>10.1016/S0167-8191(97)00100-2]
	17	M. Snir. On parallel searching. SIAM J. Comput., 14, 3(Aug. 1985), pp. 688--708.
	18	L. G. Valiant. Parallelism in comparison problems. SIAM Journal on Computing, 4 (1975), pp. 348--355.
	19	R. A. Wagner, Y. Han. Parallel algorithms for bucket sorting and the data dependent prefix problem. Proc. 1986 Int. Conf. on Parallel Processing, 924--930(August 1986).
	20	Avi Wigderson , David Zuckerman, Expanders that beat the eigenvalue bound: explicit construction and applications, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.245-251, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167163]