Optimal parallel selection

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Optimal parallel selection

Full text

Pdf (146 KB)

Source

ACM Transactions on Algorithms (TALG) archive
Volume 3 , Issue 4 (November 2007) table of contents

Article No. 38

Year of Publication: 2007

ISSN:1549-6325

Author

Yijie Han

University of Missouri at Kansas City, Kansas City, MO

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 73, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

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

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1290672.1290675 What is a DOI?

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	Ajtai, M. 1994. Recursive construction for 3-regular expanders. Combinatorica 14, 4, 379--416.
	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	Blum, M., Floyd, R. W., Pratt, V., Rivest, R. L., and Tarjan, R. E. 1973. Time bounds for selection. J. Comput. Syst. Sci. 7, 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	Chong, K. W., Han, Y., Igarashi, Y., and Lam, T. W. 1999. Improve parallel computation with fast integer sorting. In Proceedings of the 5th International Conference on Computing and Combinatorics. Lecture Notes in Computer Sciecne, vol. 1627, Springer, 452--461.
	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	Fürer, M., and Raghavachari, B. 1996. Parallel edge coloring approximation. Parallel Proc. Lett. 6, 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	Yijie Han, Optimal parallel selection, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	13	Shuji Jimbo , Akira Maruoka, Expanders obtained from affine transformations, Combinatorica, v.7 n.4, p.343-355, Dec, 1987 [doi>10.1007/BF02579322]
	14	Magulis, G. A. 1973. Explicit construction of concentrators. Problemy Peredachi Informatsii 9, 4, 71--80.
	15	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]
	16	Reischuk, R. 1985. Probabilistic parallel algorithms for sorting and selection. SIAM J. Comput. 14, 396--409.
	17	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]
	18	Snir, M. 1985. On parallel searching. SIAM J. Comput. 14, 3, 688--708.
	19	Valiant, L. G. 1975. Parallelism in comparison problems. SIAM J. Comput. 4, 348--355.
	20	Wagner, R. A., and Han, Y. 1986. Parallel algorithms for bucket sorting and the data dependent prefix problem. In Proceedings of the International Conference on Parallel Processing, 924--930.
	21	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]