2024/01/25 by Filtser, Arnold
#Combinatorics (math.CO) #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2401.14060
Given a metric space (X,dX), a (β,s,Δ)-sparse cover is a collection of clusters C⊆ P(X) with diameter at most Δ, such that for every point x∈ X, the ball BX(x,\fracΔβ) is fully contained in some cluster C∈ C, and x belongs to at most s clusters in C. Our main contribution is to show that the shortest path metric of every Kr-minor free graphs admits (O(r),O(r2),Δ)-sparse cover, and for every ε>0, (4+ε,O(\frac1ε)r,Δ)-sparse cover (for arbitrary Δ>0). We then use this sparse cover to show that every Kr-minor free graph embeds into ℓ_∞^O(\frac1ε)r+1⋅log n with distortion 3+ε (resp. into ℓ_∞^O(r2)⋅log n with distortion O(r)). Further, among other applications, this sparse cover immediately implies an algorithm for the oblivious buy-at-bulk problem in fixed minor free graphs with the tight approximation factor O(log n) (previously nothing beyond general graphs was known).