DocumentCode
2892873
Title
Using approximation algorithms to design parallel algorithms that may ignore processor allocation
Author
Goodrich, Michael T.
Author_Institution
Dept. of Comput. Sci., Johns Hopkins Univ., Baltimore, MD, USA
fYear
1991
fDate
1-4 Oct 1991
Firstpage
711
Lastpage
722
Abstract
A framework is presented for designing parallel algorithms that may ignore processor allocation. A number of fast approximation algorithms are developed, and it is shown how to use these algorithms to simulate any algorithm that fits this framework in a work-preserving fashion on a randomized CRCW PRAM. Several applications of the approach to parallel computational geometry are given
Keywords
approximation theory; computational geometry; parallel algorithms; approximation algorithms; parallel algorithms; parallel computational geometry; processor allocation; randomized CRCW PRAM; Algorithm design and analysis; Approximation algorithms; Artificial intelligence; Computational geometry; Computational modeling; Computer science; Concurrent computing; Costs; Parallel algorithms; Phase change random access memory;
fLanguage
English
Publisher
ieee
Conference_Titel
Foundations of Computer Science, 1991. Proceedings., 32nd Annual Symposium on
Conference_Location
San Juan
Print_ISBN
0-8186-2445-0
Type
conf
DOI
10.1109/SFCS.1991.185439
Filename
185439
Link To Document