Fast deterministic processor allocation

Interval alloeation has been suggested as a possible formal-ization for the PRAM ofthe (vaguely defined) proeessor allo-cation problem, which is of fundamental importanee in par-allel eomputing. The interval allocation problem is, given n nonnegative integers:1:1, •• •,:1:", to alloeate n nonoverlap-ping subarrays of sizes:1:1, •• •,:I: "!rom within a base array of 00:;=1:l:i) eells. We show that interval alloeation problems of size n ca.n be solved in O«log log n)3) time with optimal speedup on a deterministie CRCW PRAM. In addition to a: general solution to the processor allocation.problem, this implies an improved deterministie algorithm for the prob-lem of approximate summation. For both interval alloeation and approximate summation, the fastest previous determin-istie algorithms have running times of9(log n/log log n). We also describe an application to the problem of eomputing the eonnected eomponents of an undirected graph.