Theory Lunch Seminar
— 1:00pm
Location:
In Person
-
Gates Hillman 8102
Speaker:
HEATHER NEWMAN
,
Ph.D. Student, Ph.D. Program in Algorithms, Combinatorics, and Optimization, Department of Mathematical Sciences, Carnegie Mellon University,
https://hanewman.github.io/
Simultaneously Approximating all ℓp-norms in Correlation Clustering
This talk presents a universality result for correlation clustering on unweighted complete graphs. We give a combinatorial algorithm that returns a single clustering solution that is simultaneously O(1)-approximate for all ℓp-norms (1 ≤ p ≤ ∞) of the disagreement vector; in other words, a combinatorial O(1)-approximation of the all-norms objective for correlation clustering. This is the first proof that minimal sacrifice is needed in order to optimize different norms of the disagreement vector, where each norm captures some balance between average welfare (p=1) and fairness (p=∞). Prior to this work, it was not known whether an all-norms solution existed for correlation clustering, and to the best of our knowledge, this is the first all-norms result for a clustering problem more generally.
In addition, our algorithm is the first combinatorial approximation algorithm for the ℓ2-norm objective, and more generally the first combinatorial algorithm for the ℓp-norm objective when 1 < p ≤ ∞. It is also faster than all previous algorithms that minimize the ℓp -norm of the disagreement vector, with run-time O(nω), where O(nω) is the time for matrix multiplication on n by n matrices.
This is based on joint work with Sami Davies and Benjamin Moseley
Event Website:
https://www.cs.cmu.edu/~theorylunch/