- This event has passed.
IEOR Seminar Series: Sami Davies, UC Berkeley
IEOR seminars occur on Mondays throughout the Spring semester in room 3108 of Etcheverry Hall. Seminars feature leading-edge research from experts in industrial engineering and operations research who come from local, national, and international institutions. Seminars are open to students, faculty, and the public.
Location: 3108 of Etcheverry Hall
January 29 @ 3:30 - 4:45 PM
Title: One Partition Approximation All $\ell_p$ Objectives in Correlation Clustering
Abstract: Correlation clustering is a natural model arising from community detection problems. A complete graph is given with each edge labeled as either positive or negative; two vertices are connected by a positive edge when they are “similar" and want to being clustered together, while a negative edge indicates vertices that are “dissimilar" and want to be in different clusters. The goal is to find a clustering that minimizes an objective capturing the edges’ disagreements with respect to the clustering.
In this talk, we focus on objectives that minimize the $\ell_p$-norm of the disagreement vector, which is a well-studied class of objective. Our work provides the first purely combinatorial constant factor approximation algorithms for these problems. Additionally, we provide an algorithm that produces a single clustering solution that is simultaneously constant approximate for all $\ell_p$-norms of the disagreement vector. This proves that minimal sacrifice is needed in order to optimize different local norms. The combinatorial nature of our techniques lend to significant run-time improvements, with empirical results showing that our algorithms scale to larger networks that were effectively intractable for previous algorithms.
Bio: Sami Davies joined UC Berkeley EECS and the Simons Institute for the Theory of Computing as a research scientist this past fall. She previously was a post-doc at Northwestern University and received a PhD from the University of Washington in 2021.