%A Ioannis T. Christou %A Robert R. Meyer %T Optimal and Asymptotically Optimal Equi-partition of Rectangular Domains via Stripe Decomposition %D November 1995 %R 95-19 %I COMPUTER SCIENCES DEPARTMENT, UNIVERSITY OF WISCONSIN %C MADISON, WI %X We present an efficient method for assigning any number of processors to tasks associated with the cells of a rectangular uniform grid. Load balancing equi-partition constraints are observed while approximately minimizing the total perimeter of the partition, which corresponds to the amount of interprocessor communication. This method is based upon decomposition of the grid into stripes of ``optimal'' height. We prove that under some mild assumptions, as the problem size grows large in all parameters, the error bound associated with this feasible solution approaches zero. We also present computational results from a high level parallel Genetic Algorithm that utilizes this method, and make comparisons with other methods. On a network of workstations, our algorithm solves within minutes instances of the problem that would require one billion binary variables in a Quadratic Assignment formulation.