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
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;
Conference_Titel :
Foundations of Computer Science, 1991. Proceedings., 32nd Annual Symposium on
Conference_Location :
San Juan
Print_ISBN :
0-8186-2445-0
DOI :
10.1109/SFCS.1991.185439
