Theory Seminar, Wednesday Dec 25: Alon Hovav (HUJI) - Novel properties of hierarchical probabilistic partitions and their algorithmic applications

[Arnold Filtser]

Hi all,

Next week (Wed Dec 25, at 12) we will meet for our theory seminar.

Location: Building 503 room 226.

See you all there,

Arnold

https://theory.cs.biu.ac.il/

Speaker: Alon Hovav (HUJI)
Title: Novel properties of hierarchical probabilistic partitions and their algorithmic applications
Abstract: 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/euclidean 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 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. Among other results, 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.
Our results also extend to many constrained variants, improving on previous results.

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.

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 Sandip Banerjee, Yair Bartal, and Lee-Ad Gottlieb.

[Arnold Filtser]

This happens tomorrow!