Load Balancing Using Bisectors - A Tight Average-Case Analysis

In parallel computation we often need an algorithm for dividing one computationally expensive job into a fixed number, say N , of subjobs, which can be processed in parallel (with reasonable overhead due to additional communication). In practice it is often easier to repeatedly bisect jobs, i.e., split one job into exactly two subjobs, than to generate N subjobs at once. In order to balance the load among the N machines, we want to minimize the size of the largest subjob (according to some measure, like cpu-time or memory usage)