Yury Makarychev is a professor at the Toyota Technological Institute at Chicago. His primary research interests include combinatorial optimization, beyond worst-case analysis, approximation algorithms, and metric geometry. Yury received his undergraduate degree in mathematics from Moscow State University and a PhD in computer science from Princeton University. Before joining TTIC, he had spent two years at Microsoft Research as a postdoctoral fellow.

AG 1   Info

AG Audience

English

60 Minutes

Saarbrücken

We will discuss the socially fair clustering problem. In this problem, we are given a set of points in a metric space; each point is assigned to one of ℓ groups. The goal is to find a k-medians, k-means, or, more generally, ℓ_p-clustering that is simultaneously good for all of the groups. More precisely, we need to find a set of k centers C so as to minimize the maximum over all groups j of the sum ∑ d(u,C)^p, where u belongs to group j. We present an O(log ℓ / log log ℓ) approximation algorithm for this problem. We also study a more general (p, q)-fair clustering problem.

Based on joint papers with Eden Chlamtáč and Ali Vakilian

Roohani Sharma

+49 681 9325 1116

--email hidden

Zoom

988 5655 4581

passcode not visible

logged in users only

If you wish to attend the talk but do not have the password, contact Roohani Sharma at rsharma@mpi-inf.mpg.de.