A New Algorithm for Multi-objective Graph Partitioning
Abstract
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 to the tradeoffs amount the objectives, results in predictable partitionings, and is able to handle both similar and dissimilar objectives.
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 21, 1999
- Accession Number
- AD1020025
Entities
People
- George Karypis
- Kirk Schloegel
- Vipin Kumar
Organizations
- University of Minnesota