抖音网红黑料

A clustering is a partitioning into sets called clusters. The input to (unweighted) correlation clustering is an unweighted graph. We want to cluster the vertices so as to minimimize the number of edges between clusters plus the number of non-edges inside clusters.Recently there has been a lot of powerful developments for correlation clustering. The classic LP has an integrality gap of at least 2, but an efficient local search approach has gotten down to 1.85 and a new ClusterLP gets us below 1.5. The ClusterLP has exponentially many variables, and yet it can be solved in sublinear time. These modern methods also work perfectly in both parallel and dynamic settings.This is mostly a whiteboard talk where I will discuss the simple and mostly combinatorial techniques driving the above developments.

Mikkel Thorup (born 1965) has a D.Phil. from Oxford University from 1993. From 1993 to 1998 he was at the University of Copenhagen. From 1998 to 2013 he was at AT&T Labs-Research. Since 2013 he has been back as Professor at the University of Copenhagen. Since 2017, he has been a VILLUM Investigator heading Center for Basic Algorithms Research Copenhagen (BARC). Mikkel is a Fellow of the ACM and of AT&T, and a Member of the Royal Danish Academy of Sciences and Letters. He is co-winner of the 2011 MAA Robbins Award in mathematics and winner of the 2015 Villum Kann Rasmussen Award for Technical and Scientific Research, which is Denmark's biggest individual prize for research. More recently he was co-winner of the 2021 AMS-MOS Fulkerson Prize and an ACM STOC 20-year test of time award. Mikkel's main work is in algorithms and data structures, where he has worked on both upper and lower bounds. Recently one of his main focuses has been on hash functions unifying theory and practice. Mikkel prefers to seek his mathematical inspiration in nature, combining the quest with his hobbies of bird watching and mushroom picking.