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). This is in contrast to standard guarantees for probabilistic partitions which holds only in expectation. Additionally, each cell of our partition has a significantly smaller description than in previous constructions. These novel partition properties allow faster dynamic programs for a wide spectrum of fundamental problems defined by inherent or implicit sparsity. 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 so as 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 dimension. 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 power of$\alpha$), as well as aversion clustering, 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 runtimes 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.