7 października 2025 10:00
[Seminarium ZOK] Sandip Banerjee: "Novel Properties of Hierarchical Probabilistic Partitions and Their Algorithmic Applications"
We present a refined construction of hierarchical probabilistic
partitions with novel properties, substantially stronger than
previously known. Our construction provides a family of hierarchical
partitions enabling fast dynamic programming algorithms, by
guaranteeing that given a sparse set of balls, each cell of the
hierarchical partition intersects only a small number of balls. The
number of balls intersecting a cell is bounded solely as a function of
the padding parameter of the partition (which is bounded in particular
by the doubling dimension). Additionally, each cell of our partition
has a significantly smaller description than in previous
constructions.
Among our main applications highlighting the utility of the novel
properties are two well-studied clustering problems: min-sum radii
(MSR) and min-sum diameters (MSD) clustering. The input to both these
problems is a metric space and an integer k, and the goal is to
partition the space into k clusters to minimize the sum of radii or
diameters of the clusters, respectively. We apply our construction to
give dramatically improved exact and approximation algorithms for
these problems in Euclidean and doubling spaces, planar graphs, and
more general settings. In particular, we obtain for these problems the
first PTAS for doubling spaces, improving and generalizing upon the
time bounds known for Euclidean space, even achieving linear time
algorithms for fixed parameter k. We also obtain the first PTAS for
MSR for all metrics of bounded padding parameter, including planar and
minor excluded metrics.
Moreover, our results extend to constrained variants such as fair MSR
and mergeable MSR, dramatically improving upon the best known results
on these problems in low dimensions.
Our methods also extend to other clustering problems, including
alpha-MSR and alpha-MSD (where the measure is the sum of radii or
diameters raised to the power of alpha)
providing in similar settings the first QPTAS and first fixed
parameter PTAS for these problems.
Moreover, many of our clustering results extend to the corresponding
clustering problems with outliers.
Our construction applies as well to a wide range of network design
problems possessing inherent sparsity properties in doubling spaces.
Notably, we can apply our method to dramatically improve upon the best
known bounds for the traveling salesman (TSP) and Steiner-tree
problems in doubling spaces.
Similarly, we significantly improve upon the best known run-times for
Steiner forest, TSP with neighborhoods, prize collecting TSP, and
2-ECSS (two edge-connected spanning subgraph), all in doubling spaces.
Our new constructions of hierarchical probabilistic partitions present
a major simplification of previous methods, and provide a more natural
and useful tool for future applications.
Joint work with Yair Bartal, Lee-Ad Gottlieb and Alon Hovav.
Link: https://ieeexplore.ieee.org/document/10756173