Theory Seminar, Wednesday April 10 (at 14 - note different time): Ameet Gadekar (BIU) - Parameterized Approximation Schemes for Clustering with General Norm Objectives
2 views
Skip to first unread message
Arnold Filtser
Apr 7, 2024, 3:35:35 AMApr 7
to BIU Theory Seminar, Amit Gadekar
Hi all,
This Wednesday, (April 10), at 14:00 (note different time) we will meet for our theory seminar with a talk by Ameet Gadekar.
I will present a clean and simple EPAS that settles more than ten clustering problems (across multiple well-studied objectives as well as metric spaces) and unifies well-known EPASes. Our algorithm gives EPASes for a large variety of clustering objectives (for example, k-means, k-center, k-median, priority k-center, ℓ-centrum, ordered k-median, socially fair k-median aka robust k-median, or more generally monotone norm k-clustering) and metric spaces (for example, continuous high-dimensional Euclidean spaces, metrics of bounded doubling dimension, bounded treewidth metrics, and planar metrics), and is essentially oblivious to the underlying objective and metric space.
Key to our approach is a new concept that we call bounded ϵ-scatter dimension—an intrinsic complexity measure of a metric space that is a relaxation of the standard notion of bounded doubling dimension.
This is a joint work with Fateme Abbasi, Sandip Banerjee, Jarosław Byrka, Parinya Chalermsook, Kamyar Khodamoradi, Dániel Marx, Roohani Sharma, and Joachim Spoerhase.
This Wednesday, (April 10), at 14:00 (note different time) we will meet for our theory seminar with a talk by Ameet Gadekar.
Ameet recently joined BIU algorithms group, and the seminar is a great opportunity to meet Ameet, and hear about his excellent work. Ameet will present a recent work published in FOCS 2023.
Location: Building 503 room 226.
Speaker: Ameet Gadekar
Title: Parameterized Approximation Schemes for Clustering with General Norm Objectives
Abstract: In this talk, we consider the well-studied algorithmic regime of designing a (1+ϵ)-approximation algorithm for a k-clustering problem that runs in time f(k,ϵ)poly(n) (sometimes called an efficient parameterized approximation scheme or EPAS for short). Notable results of this kind include EPASes in the high-dimensional Euclidean setting for k-center [Badŏiu, Har-Peled, Indyk; STOC'02] as well as k-median, and k-means [Kumar, Sabharwal, Sen; J. ACM 2010]. However, existing EPASes handle only basic objectives (such as k-center, k-median, and k-means) and are tailored to the specific objective and metric space.
Title: Parameterized Approximation Schemes for Clustering with General Norm Objectives
Abstract: In this talk, we consider the well-studied algorithmic regime of designing a (1+ϵ)-approximation algorithm for a k-clustering problem that runs in time f(k,ϵ)poly(n) (sometimes called an efficient parameterized approximation scheme or EPAS for short). Notable results of this kind include EPASes in the high-dimensional Euclidean setting for k-center [Badŏiu, Har-Peled, Indyk; STOC'02] as well as k-median, and k-means [Kumar, Sabharwal, Sen; J. ACM 2010]. However, existing EPASes handle only basic objectives (such as k-center, k-median, and k-means) and are tailored to the specific objective and metric space.
I will present a clean and simple EPAS that settles more than ten clustering problems (across multiple well-studied objectives as well as metric spaces) and unifies well-known EPASes. Our algorithm gives EPASes for a large variety of clustering objectives (for example, k-means, k-center, k-median, priority k-center, ℓ-centrum, ordered k-median, socially fair k-median aka robust k-median, or more generally monotone norm k-clustering) and metric spaces (for example, continuous high-dimensional Euclidean spaces, metrics of bounded doubling dimension, bounded treewidth metrics, and planar metrics), and is essentially oblivious to the underlying objective and metric space.
Key to our approach is a new concept that we call bounded ϵ-scatter dimension—an intrinsic complexity measure of a metric space that is a relaxation of the standard notion of bounded doubling dimension.
This is a joint work with Fateme Abbasi, Sandip Banerjee, Jarosław Byrka, Parinya Chalermsook, Kamyar Khodamoradi, Dániel Marx, Roohani Sharma, and Joachim Spoerhase.
Arnold Filtser
Apr 10, 2024, 6:01:43 AMApr 10
to BIU Theory Seminar, Amit Gadekar
The seminar starts in one hour!
See you there.
Reply all
Reply to author
Forward
0 new messages