Graphs and Hypergraphs are ubiquitous for modelling problems in Computer Science and therefore play an important role for all kinds of optimization problems. The goal in a cut problem is to partition the vertex set of a graph/hypergraph into two or more pieces such that e.g. the total weight of edges between different pieces is minimized or maximized (of course, usually on has additional side constraint for the pieces as e.g., minimum/maximum size etc.).
Cut problems appear in a variety of different areas in Computer Science as e.g. computer graphics (image segmentation), machine learning (classification tasks), distributed computing (scheduling parallel applications), networks (identifying bottlenecks), chip layout (VLSI design) etc.
This seminar aims to systematically review different type of approaches towards solving cut problems in graphs and hypergraphs, and to give theoretical understanding of the complexity of these problems in terms of their approximability.
The seminar will be held in a block at two dates during the semester.
The seminar talks can be presented in German or English, depending on the preferences of the students.