Random Rates for 0-Extension and Low-Diameter Decompositions

Consider the problem of partitioning an arbitrary metric space into pieces of diameter at most ∆, such every pair of points is separated with relatively low probability. We propose a rate-based algorithm inspired by multiplicatively-weighted Voronoi diagrams, and prove it has optimal trade-offs. This also gives us another algorithm for the 0-extension problem