A New Algorithm for Multi-objective Graph Partitioning

Abstract

Recently, a number of graph partitioning applications have emerged with addtional requirements that the traditional graph partitioning model alone cannot effectively handle. One such class of problems is those in which multiple objectves, each of which can be modeled as a sum of weights of the edges of a graph, must be simultaneously optimized. This class of problems must be solved utilizing a multi-objective graph partitioning algorithm. In this paper, we describe a new algorithm for computing partitionings for multi-objective graphs. We explain how this scheme is able to handle the class of problems in which the objectives represent similar quantities, as well as, the class of problems in which the objectives represent dissimilar quantitites. We show that our multi-objective graph partitioning algorithm is better able to compute partitionings based on a user-supplied preference vector than partitioning with respect to a single objective only. We also show that by modifyig the input preference vector, the multi-objective graph partitioning algorithm is able to gracefully tradeoff increases in one or more objectives for decreases in ther objectives. This gives the user a fine-tuned control of the tradeoffs among the objectives.