Konstantinos Ameranis: Hypergraph Cuts, Flows and Ratios

Monday 11/29

12:30 -13:30 pm

Speaker: Konstantinos Ameranis

Room: JCL 298

Zoom link


Hypergraph Cuts, Flows and Ratios


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.

1 Like