Algorithms for Generalized Clustering: Min-Max Objective to Cascaded Norms

Speaker: Ali Vakilian , TTIC

Date: Wednesday, December 06, 2023

Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: 32-G575

Event Type: Seminar

Room Description: 32-G575

Host: Noah Golowich, MIT

Contact: Noah Golowich, nzg@csail.mit.edu

Relevant URL:

Speaker URL: http://www.mit.edu/~vakilian/

Speaker Photo:
None

Reminders to: theory-seminars@csail.mit.edu, seminars@csail.mit.edu

Reminder Subject: TALK: Ali Vakilian: Algorithms for Generalized Clustering: Min-Max Objective to Cascaded Norms

Abstract: In this talk, I will consider the k-clustering problem with min-max objective: Given an input set of points P partitioned into L predefined groups, the aim is to find a k-clustering that minimizes the maximum average clustering cost (e.g., k-means cost) across these groups, reflecting fairness in applications like polling station or vaccination sites placement. I present a O(log L/ log log L)-approximation for the clustering problem with min-max objective, which exponentially improves over the previously known O(L)-approximation and is optimal up to a constant factor.

Moreover, I will discuss the generalization of the problem to (p,q)-cascaded norms and arbitrary weight functions over the points. As an application, this allows a “relaxed” way of enforcing the fairness requirement, as its objective interpolates between the objective of classic k-clustering and that of socially fair clustering. Moreover, the problem is closely related to other well-known problems in combinatorial optimization such as densest k-subgraph and min-k union.

Bio: Ali Vakilian is a Research Assistant Professor at TTIC. His research interests include algorithms for massive data, learning-augmented algorithms, and algorithmic fairness. Ali received his Ph.D. from MIT, where he was advised by Erik Demaine and Piotr Indyk. He completed his MS studies at UIUC where he was a recipient of the Siebel Scholar award.

Research Areas:
Algorithms & Theory, AI & Machine Learning

Impact Areas:
Big Data

See other events that are part of the Algorithms and Complexity Seminar 2023.

Created by Noah Golowich at Wednesday, December 06, 2023 at 1:26 AM.