Monday 11/29
12:30 -13:30 pm
Speaker: Konstantinos Ameranis
Room: JCL 298
Title:
Hypergraph Cuts, Flows and Ratios
Abstract:
Graph cuts are important to many applications, vision, image segmentation, job scheduling, routing. First I want to talk about the optimization problem that defines a cut, how a flow problem is the dual of a cut problem and why minimum cut is not really an interesting problem. Instead, minimum ratio cut is much more interesting, but also NP-Complete. There are different variations of ratio cut problems depending on whether we care about balance and if the problem can cut edges, nodes or both. A natural extension is hypergraph cut ratios. Using different definitions of when a hyperedge is full leads to different hypergraph expansions that change the cut notion. Finally, I want to talk about algorithms and available software, their strengths and weaknesses.
Speaker bio:
Konstantinos is a third year PhD student in Convex Optimization and Spectral Graph Theory working with Lorenzo Orecchia. He received his integrated MS from National Technical University of Athens in 2018.