BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260620T183325Z
UID:Seminar-ACTO-1251@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Nikhil Mande:MAILTO:Nikhil.Mande@liverpool
DTSTART:20241009T140000
DTEND:20241009T150000
SUMMARY:Algorithms, Complexity Theory and Optimisation Series
DESCRIPTION:Joachim Spoerhase: Parameterized Approximation Schemes for Clustering with General Norm Objectives\n\nWe consider the well-studied algorithmic regime of designing a (1+epsilon)-approximation algorithm for a k-clustering problem that runs in time f(k,epsilon)poly(n) (sometimes called an efficient parameterized approximation scheme or EPAS for short). Notable previous results of this kind include EPASes in the high-dimensional Euclidean setting fork-center as well as k-median, and k-means. 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.  \n\nOur main contribution is a clean, simple, and unified algorithm that yields an EPAS for a large variety of clustering objectives (for example, k-means, k-center, k-median, priority k-center, l-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 which is (almost) entirely oblivious to the underlying objective and metric space.\n\nKey to our approach is a new concept that we call bounded epsilon-scatter dimension — an intrinsic complexity measure of a metric space that is a relaxation of the standard notion of bounded doubling dimension.  \n\nThis is joint work with Fateme Abbasi, Sandip Banerjee, Jarosław Byrka, Parinya Chalermsook, Ameet Gadekar, Kamyar Khodamoradi, Dániel Marx, and Roohani Sharma\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1251
LOCATION:Ashton Building,  Meeting room 208
END:VEVENT
END:VCALENDAR