Applications of the ham sandwich theorem to multiconstraint load balancing problems.

Abstract

When one endeavors to make a serious study of parallel algorithms, the problem of load balancing inevitably presents itself. Load balancing is the process of dividing a problem or subproblem among a number of processors at hand such that the running time of this problem or subproblem when executed in parallel is minimized. An inadequacy of existing load balancing algorithms is that they only balance a single aspect of a problem. There exist certain practical applications with more than one aspect requiring balancing, and these aspects are not always independent; they cannot always be balanced separately. An ideal balancing of one portion of a problem could result in a hideous division of labor for another phase. We represent such a load balancing situation as a data structure called a <italic>k</italic>-weighted geometric graph. A <italic>k</italic>-weighted geometric graph is a directed graph with each edge associated with a nonnegative weight, and each vertex associated with a position and with <italic>k</italic> distinct nonnegative weights. The problem of partitioning a <italic>k</italic>-weighted geometric graph into m subgraphs corresponds to the problem of dividing among <italic> m</italic> processors the work of a parallel application with <italic>k</italic> distinct aspects requiring balancing. Ideally, the sum of any of the <italic> k</italic> weights within a partition should be reasonably close to the sum of that weight within any other partition. When <italic>k</italic> = 2 and the 2-weighted graph corresponding to a certain load-balancing situation can be embedded in the plane in such a way that edges are more likely to connect nearby vertices than distant ones, a good division can be determined by an algorithm I present based upon the Ham Sandwich Theorem. The Ham Sandwich Theorem guarantees that for any two sets of weighted discrete points in the plane, the plane can be divided by a single line so that each resulting open half-plane contains no more than half of the weight of either set. I use a prune-and-search technique to find such a ham sandwich cut dividing the weights of a 2-weighted graph embedded in the plane. I use recursive bisection to divide a graph into more than two pieces. I demonstrate that this algorithm runs in asymptotic linear expected running time, and has a good real running time in practice. I also present several variants of this algorithm designed to improve other aspects of the algorithm, such as running time and edge-cuts. Recursive bisection is ineffective for dividing a graph into a number of pieces that is not a power of 2. With this in mind, I develop and prove a new mathematical tool---the Submarine Sandwich Theorem---to handle cases in which a set of points is not to be divided exactly in half, a situation for which the Ham Sandwich Theorem is inadequate. I also describe algorithms based upon this theorem.