Sparse Partitions (Extended Abstract)
📜 Abstract
This abstract presents a collection of clustering and decomposition techniques enabling the construction of sparse and locality preserving representations for arbitrary networks. These new clustering techniques have already found several powerful applications in the area of distributed network algorithms. Two of these applications are described in this abstract, namely, routing with polynomial communication-space tradeoff and online tracking of mobile users.
✨ Summary
The paper develops clustering and decomposition methods for representing arbitrary weighted networks with connected, locality-preserving clusters. Its central objective is to balance two competing parameters: cluster radius, which controls locality and communication time, and sparsity, which controls the amount of state maintained by individual vertices.
| The main construction repeatedly merges overlapping clusters to obtain coarsenings with controlled radius growth and reduced overlap. For a parameter (k), the maximum-degree coarsening achieves radius at most ((2k-1)) times the original radius and maximum cover degree at most (2k | \mathcal{S} | ^{1/k}). Related constructions provide improved bounds for average degree, vertex-degree, and cluster-degree measures. The paper also establishes lower bounds showing that the sparsity–radius tradeoff is close to optimal for some graph families. |
The framework is used to construct regional matchings, sparse spanners, low-diameter separators, and sparse tree covers. Two distributed-systems applications are developed: a hierarchical routing scheme with stretch (O(k^2)) and per-vertex memory (O(n^{1/k}\log^2 n\log \operatorname{Diam}(G))), and a directory structure for mobile users with (O(\log^2 n)) find- and move-stretch and total memory (O(N\log^2 n+n\log^3 n)).
Subsequent research explicitly identifies Awerbuch and Peleg as the first authors to study sparse covers and describes their constructions as foundational for later sparse-partition work. Later results used their sparse-cover construction as an integral component of universal spanning-tree and universal traveling-salesperson algorithms. (drops.dagstuhl.de) A subsequent SIAM Journal on Computing paper developed near-linear-time constructions of sparse neighborhood covers and connected them to improvements for network decompositions, approximate shortest paths, and graph spanners, while citing this paper as an antecedent. (epubs.siam.org) The search identified substantial influence on subsequent theoretical research, but no specific industrial deployment directly attributable to this paper.