If you consider participating in this lab, please write an informal application e-mail to Jonas Charfreitag. This lab has an upper limit on the number of participants; please mention the semester you finished the masters course “Algorithms for Data Analysis” and a list of other algorithmic related courses you attended. Deadline for all applications is 28.02.2023.

There will be an introductory workshop on tools for algorithm-engineering and C++; most probably in the last week of March.

Optimal solutions for the Multiterminal-Cut-Problem using Integer-Linear Programming techniques. The problem is related to graph coloring and maximum cut.

Given a Graph G=(V,E) and a subset of vertices T called terminals, find a cut of minimum weight, separating all terminals from one another.

While this is generally a hard problem, we will develop a program to calculate provably optimal solutions as fast as possible.

Some related literature:

• https://epubs.siam.org/doi/epdf/10.1137/S0097539792225297
• https://www.sciencedirect.com/science/article/abs/pii/S0377221703008348
• https://epubs.siam.org/doi/abs/10.1137/1.9781611976007.4
• https://epubs.siam.org/doi/abs/10.1137/1.9781611976830.10
• https://openaccess.thecvf.com/content_CVPR_2019/html/Lange_Combinatorial_Persistency_Criteria_for_Multicut_and_Max-Cut_CVPR_2019_paper.html
• https://link.springer.com/article/10.1007/BF01581239

_{DozentInnen: Mutzel, Charfreitag}