Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
  
 

Research Seminar (Summer Term 2021)

<previous seminar | next seminar>

COVID-19 and virtual seminars

Due to the current situation we are not hosting seminars at the HPI anymore. Instead, we host virtual seminars via zoom. If you want to join the seminar on short notice or if you do not want to subscribe to the mailing list, please send an email to Katrin.Casel(at)hpi.de or to Andreas.Goebel(at)hpi.de.

Description

A series of talks on current research and interesting topics in algorithm engineering and theoretical computer science. Everyone is welcome to attend talks. 

If you want to give a talk about a topic in algorithm engineering or theoretical computer science, please write an e-mail to Katrin Casel or to Andreas Göbel.

Announcements

For announcements of talks, subscribe to our mailing list.

Talks (click on title to show abstract)

DateRoom SpeakerTitle
07.04. 10:15virtualMichael Vaichenker
As fair clustering is quite a popular topic many questions regarding it are already answered. However, the problem of finding a Fair Ratio-Cut remains mostly a blank slate. Fair Ratio-Cut is a cut in a colored graph that minimizes the ratio between edges cut and the balance of the cut, while containing each color to equal amounts within each resulting cluster. The goal of my thesis is to contribute first theoretical results for this problem and I will present to you some of the results I already found, including the hardness of the "many colors case".
16.04. 11:00virtualNicolas Klodt, Lars Seifert, Arthur Zahn

Chromatic Correlation Clustering (CCC) models clustering of objects with categorical pairwise relationships. The model can be viewed as clustering the vertices of a graph with edge-labels (colors). Bonchi et al. [KDD 2012] introduced it as a natural generalization of the well studied problem Correlation Clustering (CC), also known as Cluster Editing.

Our main theoretical contribution is an alternative analysis of the famous Pivot algorithm for CC. We show that, when simply run color-blind, Pivot is also a linear time 3-approximation for CCC. The previous best theoretical results for CCC were a 4-approximation with a high-degree polynomial runtime and a linear time 11-approximation, both by Anava et al. [WWW 2015].

While this theoretical result justifies Pivot as a baseline comparison for other heuristics, its blunt color-blindness performs poorly in practice. We develop a color-sensitive, practical heuristic we call Greedy Expansion that empirically outperforms all heuristics proposed for CCC so far, both on real-world and synthetic instances.

Further, we propose a novel generalization of CCC allowing for multi-labelled edges. We argue that it is more suitable for many of the real-world applications and show that running the color blind algorithm does still result in a 3-approximation.

23.04. 11:00virtualJohn Sylvester
TBA
09.07. 11:00virtual Karen Seidel
TBA