Random Rates for 0-Extension and Low-Diameter Decompositions

Abstract

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 logarithmic approximation algorithm for the 0-extension problem.