论文标题
散射和稀疏分区及其应用
Scattering and Sparse Partitions, and their Applications
论文作者
论文摘要
加权图$ g $的分区$ \ MATHCAL {p} $是$（σ，τ，δ）$ - 如果每个群集最多都有直径为$δ$，而每个半径$Δ/σ$相交的每个群集最多$τ$ clusters。同样，$ \ Mathcal {p} $是$（σ，τ，δ）$ - 散射，如果对于球，我们要求最多的每一个最短的长度路径，最多$Δ/σ$在最多$τ$ clusters上相交。给定一个$（σ，τ，δ）$ - 所有$δ> 0 $的稀疏分区，Jia等给出了图形$ g $。 [stoc05]用拉伸$ o（τσ^2 \log_τn）$构建了通用施泰纳树问题（以及通用TSP）的解决方案。给定一个$ g $，该图$ g $承认所有$δ> 0 $的$（σ，τ，δ）$ - 散射分区，我们为strave $ o（τ^3σ^3）$构建了一个解决方案。然后，我们为各种不同的图形家族构建稀疏和散射分区，为通用Steiner树和Steiner Point Removal问题获得许多新结果。
A partition $\mathcal{P}$ of a weighted graph $G$ is $(σ,τ,Δ)$-sparse if every cluster has diameter at most $Δ$, and every ball of radius $Δ/σ$ intersects at most $τ$ clusters. Similarly, $\mathcal{P}$ is $(σ,τ,Δ)$-scattering if instead for balls we require that every shortest path of length at most $Δ/σ$ intersects at most $τ$ clusters. Given a graph $G$ that admits a $(σ,τ,Δ)$-sparse partition for all $Δ>0$, Jia et al. [STOC05] constructed a solution for the Universal Steiner Tree problem (and also Universal TSP) with stretch $O(τσ^2\log_τn)$. Given a graph $G$ that admits a $(σ,τ,Δ)$-scattering partition for all $Δ>0$, we construct a solution for the Steiner Point Removal problem with stretch $O(τ^3σ^3)$. We then construct sparse and scattering partitions for various different graph families, receiving many new results for the Universal Steiner Tree and Steiner Point Removal problems.
