An Application of Parallel Computation to Sequential Computation: The Problem of Cost-Effective Resource Allocation

摘要

A class of problems is demonstrated where good parallel algorithms become useful for designing efficient sequential algorithms. In particular, Valiant's parallel sorting algorithm is applied in the design of an algorithm for the problem of cost-effective resource allocation.