oxx1108 edited 4 年,8 月前
This is a past version of blog 2-hop label & cover
2-hop label: 对于某个点$w$, $L(w)=(L_{in}(w), L_{out}(w))$,In/Out为能到达$w$点/从$w$点出发的所有结点以及其最短路的长度。
2-hop cover: 求最少需要多少的 2-hop label(可以看作在原图上加一些边,要求最少的边) 能够满足,对于任意一对点$u, v$,存在一个点$w$,满足$dist(u, v) = edge(u, w) + edge(w, v)$。
解法:
2-hop cover 可以看作 weighed set cover 问题。所需要覆盖的 set 为所有两两的点对${(u, v)}$。用来覆盖的集合为$S{C_{in}, w, C_{out}}={(u, v) | u \in C_{in}, v \in C_{out}, w \in B_{uv}}$, $B_{uv}$是$u$到$v$最短路的路径。$w(S) = |S{C_{in}, w, C_{out}}| = |C_{in}| + |C_{out}|$.
那么用 weighed set cover 问题的贪心法可以求得 log 的近似解。
首先,可以明确的是最终答案最多需要不超过 $|V|$ 个set,因为对于相同的 $w$ 可以合并。
那么贪心法求的就是每次并入 $\frac{|S{C_{in}, w, C_{out}} \cap T^\prime|}{|C_{in}| + |C_{out}|}$ 最大的集合,其中$T^\prime$是没有被选中的点对(边)。