Vortrag von Mag. Dipl.-Ing. Melanie Siebenhofer im Doctoral Seminar Mathematics: „Finding the Right Balance: Trade-Offs in Minimum Cut Edge Expansion with SDPs“
The edge expansion is an NP-hard to compute graph constant and gives us information about the connectivity of a graph. It is the minimum ratio of the number of edges joining two sets and the size of the smaller set over all possible non-trivial bipartitions of the vertices. The edge expansion of a connected graph is small if there is a bottleneck between two large parts of the graph. Because of this fact, it is for example used in clustering or network design. There are some heuristics to find a bipartition, like the well-known spectral clustering.
This fractional optimization problem does not fit into the typical setting like other graph constants as the maximum cut which are NP-hard to compute. We propose different strategies to compute the edge expansion efficiently. One is to divide the problem into subproblems of an easier-to-handle type. Another one is to apply Dinkelbach's algorithm for fractional programming. Furthermore, we investigate the conjecture of Mihail and Vazirani, stating that the edge epxansion of the graph from a 0/1-polytope is at least 1, using our techniques.
Veranstalter
Vortragende(r)
Melanie Siebenhofer (Universität Klagenfurt)
Kontakt
Marie Biedermann (marie [dot] biedermann [at] aau [dot] at)
Ähnliche Veranstaltungen
