AG 1, AG 2, AG 3, INET, AG 4, AG 5, D6, SWS, RG1, MMCI   Info

AG Audience

English

30 Minutes

In the Correlation Clustering problem, we are given a complete graph, where each edge is labeled with either a plus or minus sign. The goal is to compute a clustering (partition of the nodes) that minimizes the number of plus edges across different clusters and the number of minus edges within clusters. Correlation Clustering is one of the most widely studied clustering formulations, having found success in modeling a variety of real-world clustering problems. In the constrained version of this problem, the goal is to compute a clustering that satisfies additional hard constraints requiring certain pairs to be in the same cluster and certain pairs to be in different clusters. This models, for example, situations where we want to incorporate expert knowledge.

Constrained Correlation Clustering is APX-Hard, and the best known approximation factor is 3 (van Zuylen et al. [SODA ‘07]). In this work, we present an algorithm that gives a better-than-2-approximation, thereby significantly improving the state-of-the-art. The novelty of our paper is that we show how two seemingly unrelated techniques for unconstrained Correlation Clustering (LP and local search) can in fact be combined to solve the constrained version of the problem. Interestingly, despite being a combination of two existing algorithms, our algorithm has a simpler analysis than either of its individual components.

Ina Geisler

+49 681 9325 1802

--email hidden

Zoom

passcode not visible

logged in users only