TY - GEN

T1 - A new algorithm for multi-objective graph partitioning

AU - Schloegel, Kirk

AU - Karypis, George

AU - Kumar, Vipin

PY - 1999

Y1 - 1999

N2 - Recently, a number of graph partitioning applications have emerged with additional requirements that the traditional graph partitioning model alone cannot effectively handle. One such class of problems is those in which multiple objectives, 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 can be solved utilizing a multi-objective graph partitioning algorithm. We present a new formulation of the multi-objective graph partitioning problem and describe an algorithm that computes partitionings with respect to this formulation. We explain how this algorithm provides the user with a fine-tuned control of the tradeoffs among the objectives, results in predictable partitionings, and is able to handle both similar and dissimilar objectives. We show that this algorithm is better able to find a good tradeoff among the objectives than partitioning with respect to a single objective only. Finally, we show that by modifying the input preference vector, the multi-objective graph partitioning algorithm is able to gracefully tradeoff decreases in one objective for increases in the others.

AB - Recently, a number of graph partitioning applications have emerged with additional requirements that the traditional graph partitioning model alone cannot effectively handle. One such class of problems is those in which multiple objectives, 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 can be solved utilizing a multi-objective graph partitioning algorithm. We present a new formulation of the multi-objective graph partitioning problem and describe an algorithm that computes partitionings with respect to this formulation. We explain how this algorithm provides the user with a fine-tuned control of the tradeoffs among the objectives, results in predictable partitionings, and is able to handle both similar and dissimilar objectives. We show that this algorithm is better able to find a good tradeoff among the objectives than partitioning with respect to a single objective only. Finally, we show that by modifying the input preference vector, the multi-objective graph partitioning algorithm is able to gracefully tradeoff decreases in one objective for increases in the others.

UR - http://www.scopus.com/inward/record.url?scp=84878644833&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84878644833&partnerID=8YFLogxK

U2 - 10.1007/3-540-48311-x_42

DO - 10.1007/3-540-48311-x_42

M3 - Conference contribution

AN - SCOPUS:84878644833

SN - 3540664432

SN - 9783540664437

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 322

EP - 331

BT - Euro-Par 1999 - Parallel Processing

PB - Springer Verlag

T2 - 5th International Conference on Parallel Processing, Euro-Par 1999

Y2 - 31 August 1999 through 3 September 1999

ER -