BEGIN:VCALENDAR
VERSION:2.0
PRODID:Linklings LLC
BEGIN:VTIMEZONE
TZID:America/Chicago
X-LIC-LOCATION:America/Chicago
BEGIN:DAYLIGHT
TZOFFSETFROM:-0600
TZOFFSETTO:-0500
TZNAME:CDT
DTSTART:19700308T020000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=2SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0500
TZOFFSETTO:-0600
TZNAME:CST
DTSTART:19701101T020000
RRULE:FREQ=YEARLY;BYMONTH=11;BYDAY=1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20211207T055338Z
LOCATION:Ferrara Theatre
DTSTART;TZID=America/Chicago:20211116T153000
DTEND;TZID=America/Chicago:20211116T161500
UID:submissions.supercomputing.org_SC21_sess245_awd102@linklings.com
SUMMARY:Multilevel Algorithms for Multi-Constraint Graph Partitioning
DESCRIPTION:Awards Presentation, Test of Time\n\nMultilevel Algorithms for
Multi-Constraint Graph Partitioning\n\nKarypis, Kumar\n\nTraditional grap
h partitioning algorithms compute a k-way partitioning of a graph such tha
t the number of edges that are cut by the partitioning is minimized and ea
ch partition has an equal number of vertices. The task of minimizing the e
dge-cut can be considered as the objective and the requirement that the pa
rtitions will be of the same size can be considered as the constraint. In
this paper we extend the partitioning problem by incorporating an arbitrar
y number of balancing constraints. In our formulation, a vector of weights
is assigned to each vertex, and the goal is to produce a k-way partitioni
ng such that the partitioning satisfies a balancing constraint associated
with each weight, while attempting to minimize the edge-cut.\n\nApplicatio
ns of this multi-constraint graph partitioning problem include parallel so
lution of multi-physics and multi-phase computations, that underlay many e
xisting and emerging large-scale scientific simulations. We present new mu
lti-constraint graph partitioning algorithms that are based on the multile
vel graph partitioning paradigm. Our work focuses on developing new types
of heuristics for coarsening, initial partitioning, and refinement that ar
e capable of successfully handling multiple constraints. We experimentally
evaluate the effectiveness of our multi-constraint partitioners on a vari
ety of synthetically generated problems.\n\nTag: Algorithms, Applications,
Computational Science, Scientific Computing\n\nRegistration Category: Tec
h Program Reg Pass
END:VEVENT
END:VCALENDAR