Veranstaltungsort
https://classroom.aau.at/b/anw-ezd-k9g
Universität Klagenfurt
Veranstalter
Institut für Mathematik
Beschreibung
Title: Building upper bounds for graph partitioning problems
Abstract:
The graph partitioning problem asks to find a partition of the vertices of
a graph that has the minimum total weight for all the edges cut by the
partitions. Is is an NP-hard problem and it is computationally expensive to
solve the problem by heuristics when the the graph size increases. In this talk
we present ways to obtain tight lower bounds by forming the semidefinite
programming (SDP) relaxations for the graph partitioning problem and
then build feasible solutions based on the SDP solution. First numerical
experiments demonstrate that we find high quality bounds with reasonable
computational costs.
Vortragende(r)
Shudian Zhao
Kontakt
senka haznadar (senka [dot] haznadar [at] aau [dot] at)
