Multi.Objective Hypergraph Partitioning Algorithms for Cut and Maximum Subdomain Degree Minimization

In this paper we present a family of multi-objective hypergraphpartitioning algorithms based on the multilevel paradigm, whichare capable of producing solutions in which both the cut and themaximum subdomain degree are simultaneously minimized. Thistype of partitionings are critical for existing and emerging applications in VLSI CAD as they allow to both minimize and evenly distribute the interconnects across the physical devices. Our experimental evaluation on the ISPD98 benchmark show that ouralgorithms produce solutions that when compared against thoseproduced by hMETIS have a maximum subdomain degree that isreduced by up to 35% while achieving comparable quality in terms of cut.