Clustering with Sum of Radii: From Classical to Modern Constraints

14^th July 2026, 13:00 Brodie Tower room 107
Ameet Gadekar
CISPA Helmholtz Center for Information Security

Abstract

How should we deploy a campus-wide Wi-Fi network using only a limited number of access points while minimizing the total transmission power? Since the transmission power required by an access point increases rapidly with its coverage radius, this naturally leads to the Sum of Squared Radii objective. Its closely related counterpart, Sum of Radii, has emerged as a fundamental optimization problem in clustering and has inspired a rich line of algorithmic research.

In this talk, I will first survey the computational landscape of Sum of Radii and its modern variants, including capacities, outliers, and fairness, which have received significant attention in recent years, particularly from the perspective of parameterized approximation algorithms. I will then focus on the capacitated variants of these problems, which provides a more realistic model of the motivating Wi-Fi deployment scenario by limiting the number of devices that each access point can serve. The second half of the talk will present the main ideas behind our recent work, which significantly improves the previous best approximation guarantees for these problems.