高级算法 (Spring 2026)/作业3

小题均为提示性质，小题越多越简单。

低 [math]\displaystyle{ \ell_\infty }[/math]-norm 对高斯 JL 变换没有帮助

令 [math]\displaystyle{ \Pi \in \mathbb R^{m\times d} }[/math] 是一个高斯 Johnson-Lindenstrauss 变换，其中每个元素独立服从 [math]\displaystyle{ N(0,1/m) }[/math]。给定任意固定单位向量 [math]\displaystyle{ x\in\mathbb S^{d-1} }[/math]。

1. 证明 [math]\displaystyle{ \Pi x }[/math] 的每个坐标都独立服从 [math]\displaystyle{ N(0,1/m) }[/math]。
2. 证明 [math]\displaystyle{ \|\Pi x\|_2^2 }[/math] 与 [math]\displaystyle{ \frac{1}{m}\chi_m^2 }[/math] 同分布。因此 [math]\displaystyle{ \|\Pi x\|_2 }[/math] 的分布与 [math]\displaystyle{ \|x\|_\infty }[/math] 无关。
3. 解释为什么如果使用高斯 JL 变换，即使 [math]\displaystyle{ x }[/math] 满足很强的平坦性条件，例如 [math]\displaystyle{ \|x\|_\infty \le O(1/\sqrt d) }[/math]，为了保证 [math]\displaystyle{ \mathbb P[\|\Pi x\|_2^2-1|\gt \epsilon]\le \delta }[/math]，所需的目标维数仍然是 [math]\displaystyle{ m=\Theta(\epsilon^{-2}\log(1/\delta)) }[/math]。
4. 对比坐标采样型（即 [math]\displaystyle{ \Pi x }[/math]直接随机输出 [math]\displaystyle{ x }[/math]的某几个维度）降维，简要解释为什么低 [math]\displaystyle{ \ell_\infty }[/math]-norm 对坐标采样有帮助，但对高斯 JL 变换没有帮助。

torus 上的随机网格 LSH

考虑 metric space [math]\displaystyle{ ( [0,n]^d,d_{\mathrm{torus}} ) }[/math]，其中距离定义为 [math]\displaystyle{ d_{\mathrm{torus}}(x,y)=\sqrt{\sum_{i=1}^d \min{|x_i-y_i|,n-|x_i-y_i|}^2} }[/math]。给定网格宽度 [math]\displaystyle{ w\gt 0 }[/math]。随机选择平移向量 [math]\displaystyle{ s\in[0,w)^d }[/math]，并定义 hash function [math]\displaystyle{ h_s(x)=(\lfloor (x_1+s_1)/w\rfloor,\dots,\lfloor (x_d+s_d)/w\rfloor) }[/math]，其中每个坐标都按照 torus 的方式取模。

1. 对于两个点 [math]\displaystyle{ x,y\in[0,n]^d }[/math]，记 [math]\displaystyle{ \Delta_i=\min\{|x_i-y_i|,n-|x_i-y_i|\} }[/math]。证明如果对所有 [math]\displaystyle{ i }[/math] 都有 [math]\displaystyle{ \Delta_i\lt w }[/math]，那么 [math]\displaystyle{ \mathbb P[h_s(x)=h_s(y)]=\prod_{i=1}^d (1-\Delta_i/w) }[/math]。
2. 证明如果 [math]\displaystyle{ d_{\mathrm{torus}}(x,y)\le r }[/math]，那么 [math]\displaystyle{ \mathbb P[h_s(x)=h_s(y)]\ge 1-\sqrt d,r/w }[/math]。提示：可以使用 [math]\displaystyle{ \sum_i\Delta_i\le \sqrt d\sqrt{\sum_i\Delta_i^2} }[/math]。
3. 解释为什么这个 LSH family 的随机桶可以看成随机平移后的 axis-aligned cube。请从“近点容易落在同一个随机集合中，远点不容易落在同一个随机集合中”的角度解释这个构造的直觉。
4. 讨论这个构造在高维空间中的局限性。特别地，当距离 [math]\displaystyle{ d_{\mathrm{torus}}(x,y) }[/math] 分散在很多个坐标上时，为什么随机网格更容易把 [math]\displaystyle{ x }[/math] 和 [math]\displaystyle{ y }[/math] 切开？
5. 设 [math]\displaystyle{ x,y }[/math] 只在一个坐标上相差 [math]\displaystyle{ r }[/math]，其他坐标完全相同。计算 [math]\displaystyle{ \mathbb P[h_s(x)=h_s(y)] }[/math]。
6. 设 [math]\displaystyle{ x,y }[/math] 在每个坐标上都相差 [math]\displaystyle{ r/\sqrt d }[/math]，因此 [math]\displaystyle{ d_{\mathrm{torus}}(x,y)=r }[/math]。在 [math]\displaystyle{ r/\sqrt d\lt w }[/math] 的条件下，计算 [math]\displaystyle{ \mathbb P[h_s(x)=h_s(y)] }[/math]，并将其写成 [math]\displaystyle{ (1-r/(w\sqrt d))^d }[/math] 的形式。
7. 比较上述两种情况。说明即使两对点的 torus 距离都等于 [math]\displaystyle{ r }[/math]，随机网格 LSH 的碰撞概率仍然可能不同。
8. 解释这说明了什么：axis-aligned grid LSH 并不是只依赖于欧氏距离的完美 LSH family，而是会受到坐标方向和维数的影响。

球面上的随机超平面 LSH

考虑球面空间 [math]\displaystyle{ (\mathbb S^{d-1},d) }[/math]，其中距离定义为 [math]\displaystyle{ d(x,y)=\arccos\langle x,y\rangle }[/math]。随机选择 [math]\displaystyle{ g\sim N(0,I_d) }[/math]，并定义 hash function [math]\displaystyle{ h_g(x)=\operatorname{sign}\langle g,x\rangle }[/math]。

1. 对任意 [math]\displaystyle{ x,y\in\mathbb S^{d-1} }[/math]，令 [math]\displaystyle{ \theta=\arccos\langle x,y\rangle }[/math]。证明 [math]\displaystyle{ \mathbb P[h_g(x)=h_g(y)]=1-\theta/\pi }[/math]。
2. 解释上述公式的几何直觉：随机超平面什么时候会把 [math]\displaystyle{ x }[/math] 和 [math]\displaystyle{ y }[/math] 分到两侧？
3. 现在使用 [math]\displaystyle{ k }[/math] 个独立随机超平面 [math]\displaystyle{ g_1,\dots,g_k }[/math]，并定义组合 hash key 为 [math]\displaystyle{ H(x)=(h_{g_1}(x),\dots,h_{g_k}(x)) }[/math]。证明 [math]\displaystyle{ \mathbb P[H(x)=H(y)]=(1-\theta/\pi)^k }[/math]。
4. 给定两个角度阈值 [math]\displaystyle{ 0\lt \theta_1\lt \theta_2\lt \pi }[/math]。令近点满足 [math]\displaystyle{ d(x,y)\le \theta_1 }[/math]，远点满足 [math]\displaystyle{ d(x,y)\ge \theta_2 }[/math]。写出这个 LSH family 的参数 [math]\displaystyle{ p_1 }[/math] 和 [math]\displaystyle{ p_2 }[/math]，并推导标准 LSH exponent [math]\displaystyle{ \rho=\log(1/p_1)/\log(1/p_2) }[/math]。

由范数保持推出内积保持

设线性映射 [math]\displaystyle{ \Pi }[/math] 对向量集合 [math]\displaystyle{ {x,y,x+y,x-y} }[/math] 都保持平方范数，即对所有 [math]\displaystyle{ v\in{x,y,x+y,x-y} }[/math] 都有 [math]\displaystyle{ (1-\epsilon)\|v\|_2^2\le \|\Pi v\|_2^2\le (1+\epsilon)\|v\|_2^2 }[/math]。

1. 使用恒等式 [math]\displaystyle{ \langle x,y\rangle=(\|x+y\|_2^2-\|x-y\|_2^2)/4 }[/math]，证明 [math]\displaystyle{ |\langle \Pi x,\Pi y\rangle-\langle x,y\rangle|\le O(\epsilon)(\|x\|_2^2+\|y\|_2^2) }[/math]。
2. 在 [math]\displaystyle{ \|x\|_2=\|y\|_2=1 }[/math] 的情况下，将上式化简为 [math]\displaystyle{ |\langle \Pi x,\Pi y\rangle-\langle x,y\rangle|\le O(\epsilon) }[/math]。
3. 解释为什么如果 JL 变换对 [math]\displaystyle{ n }[/math] 个点的所有两两距离都近似保持，那么这些点的两两内积也近似保持。
4. 进一步讨论：如果这些点都在单位球面上，那么 JL 降维之后，球面角度 [math]\displaystyle{ \arccos\langle x,y\rangle }[/math] 在什么意义下也被近似保持？

从阈值版 Approximate Near Neighbor 到 Approximate Nearest Neighbor

假设你有一个阈值版 Approximate Near Neighbor 黑盒。给定半径 [math]\displaystyle{ r }[/math] 和查询点 [math]\displaystyle{ q }[/math]，如果数据集 [math]\displaystyle{ P }[/math] 中存在点 [math]\displaystyle{ p }[/math] 满足 [math]\displaystyle{ |p-q|\le r }[/math]，那么黑盒会返回某个点 [math]\displaystyle{ p' }[/math]，并保证 [math]\displaystyle{ |p'-q|\le a r }[/math]。

现在希望用这个黑盒解决普通 Approximate Nearest Neighbor 问题。设真正最近邻距离为 [math]\displaystyle{ d^\star=\min_{p\in P}|p-q| }[/math]。我们建立一组半径 [math]\displaystyle{ r_0,r_1,r_2,\dots }[/math]，满足 [math]\displaystyle{ r_{i+1}=b r_i }[/math]。查询时，从小到大尝试这些半径，并返回第一个成功的黑盒查询结果。

1. 证明最终得到的近似比至多为 [math]\displaystyle{ ab }[/math]。
2. 如果希望最终得到 [math]\displaystyle{ c }[/math]-approximate nearest neighbor，应该如何选择 [math]\displaystyle{ a }[/math] 和 [math]\displaystyle{ b }[/math]？
3. 解释为什么常见做法中，会把阈值版 ANN 黑盒的 approximate ratio 从 [math]\displaystyle{ c }[/math] 设置为 [math]\displaystyle{ \sqrt c }[/math]。
4. 如果最近邻距离的可能范围被限制在 [math]\displaystyle{ [1,\Delta] }[/math] 中，分析需要建立多少个半径层级。

先用 JL 降维，再做随机超平面 LSH

设 [math]\displaystyle{ P\subseteq\mathbb S^{d-1} }[/math] 是 [math]\displaystyle{ n }[/math] 个单位向量。令 [math]\displaystyle{ \Pi:\mathbb R^d\to\mathbb R^m }[/math] 是一个 JL transform，并假设对所有 [math]\displaystyle{ x,y\in P }[/math]，都有 [math]\displaystyle{ \left|\|\Pi x-\Pi y\|_2^2-\|x-y\|_2^2\right|\le \epsilon }[/math]。同时假设对所有 [math]\displaystyle{ x\in P }[/math]，都有 [math]\displaystyle{ \left|\|\Pi x\|_2^2-1\right|\le \epsilon }[/math]。

1. 证明对所有 [math]\displaystyle{ x,y\in P }[/math]，都有 [math]\displaystyle{ |\langle \Pi x,\Pi y\rangle-\langle x,y\rangle|\le O(\epsilon) }[/math]。
2. 令 [math]\displaystyle{ \theta=\arccos\langle x,y\rangle }[/math]，并令 [math]\displaystyle{ \widetilde\theta=\arccos(\langle \Pi x,\Pi y\rangle/(\|\Pi x\|_2\|\Pi y\|_2)) }[/math]。在 [math]\displaystyle{ \theta }[/math] 不太接近 [math]\displaystyle{ 0 }[/math] 或 [math]\displaystyle{ \pi }[/math] 的情况下，给出 [math]\displaystyle{ |\theta-\widetilde\theta| }[/math] 的上界。
3. 解释为什么可以先对数据集 [math]\displaystyle{ P }[/math] 做 JL 降维，再在低维空间中使用随机超平面 LSH。
4. 讨论当两个点的夹角非常小时，为什么需要更小的 JL 误差才能保证角度的相对误差较好。

为什么 CountSketch 需要随机符号

考虑一个没有随机符号的 CountSketch。对每个 [math]\displaystyle{ i\in[n] }[/math]，随机选择桶 [math]\displaystyle{ h(i)\in[m] }[/math]，并令 [math]\displaystyle{ \Pi_{h(i),i}=1 }[/math]，其他位置为 [math]\displaystyle{ 0 }[/math]。 取向量 [math]\displaystyle{ x=(1,1,\dots,1)/\sqrt n }[/math]。

1. 证明 [math]\displaystyle{ \mathbb E\|\Pi x\|_2^2=1+(n-1)/m }[/math]。
2. 说明如果 [math]\displaystyle{ m=o(n) }[/math]，那么这个没有随机符号的 sketch 对该向量的范数估计会有严重偏差。
3. 现在考虑标准 CountSketch：对每个 [math]\displaystyle{ i\in[n] }[/math]，随机选择桶 [math]\displaystyle{ h(i)\in[m] }[/math]，并随机选择符号 [math]\displaystyle{ \sigma_i\in\{-1,1\} }[/math]，令 [math]\displaystyle{ \Pi_{h(i),i}=\sigma_i }[/math]，其他位置为 [math]\displaystyle{ 0 }[/math]。解释随机符号 [math]\displaystyle{ \sigma_i }[/math] 如何使不同坐标碰撞产生的交叉项在期望中相互抵消。
4. 总结随机符号在 CountSketch 中的作用：它并不能避免碰撞，但可以让碰撞带来的误差成为均值为零的随机噪声。

CountSketch OSE 的 [math]\displaystyle{ m=\Omega(d^2) }[/math] 下界

假设 [math]\displaystyle{ n\gg d }[/math]（不妨假设 [math]\displaystyle{ n\gt 2^d }[/math]）。考虑使用一个 column sparsity 只有 [math]\displaystyle{ 1 }[/math] （即，每一列只有一个非零元素） 的矩阵 [math]\displaystyle{ \Pi\in\mathbb R^{m\times n} }[/math] 进行 Oblivious Subspace Embedding (OSE)。考虑这样的随机矩阵 [math]\displaystyle{ A\in \{0,1\}^{n\times d} }[/math]： [math]\displaystyle{ A }[/math] 的每一列随机选择一个位置为 [math]\displaystyle{ 1 }[/math]，其他位置为 [math]\displaystyle{ 0 }[/math]。尝试证明，任意确定的 [math]\displaystyle{ \Pi }[/math] 为[math]\displaystyle{ A }[/math]的列空间进行子空间嵌入都至少需要 [math]\displaystyle{ m=\Omega(d^2) }[/math] ，即它作为 OSE 不可能降维到 [math]\displaystyle{ o(d^2) }[/math]。提示：尝试观察 [math]\displaystyle{ \Pi Ae_i, \Pi A(e_i+e_j) }[/math] 的 [math]\displaystyle{ \ell_2 }[/math]-norm，以及你可能需要应用 birthday paradox（随机地把 [math]\displaystyle{ d }[/math] 个球丢入 [math]\displaystyle{ m }[/math] 个桶中，那么要满足 [math]\displaystyle{ m=\Omega(d^2) }[/math] 才能使得有 [math]\displaystyle{ \Omega(1) }[/math]的概率，这 [math]\displaystyle{ d }[/math] 个球中不会有两个球被丢进了同一个桶中）。

CountSketch OSE 的 [math]\displaystyle{ m=O(d^2/\epsilon^2\delta) }[/math] 上界

令 [math]\displaystyle{ U\in\mathbb R^{n\times d} }[/math] 是一个列正交矩阵，即 [math]\displaystyle{ U^\top U=I_d }[/math]。令 [math]\displaystyle{ \Pi\in\mathbb R^{m\times n} }[/math] 是 CountSketch 矩阵：对每个原始坐标 [math]\displaystyle{ i\in[n] }[/math]，随机选择桶 [math]\displaystyle{ h(i)\in[m] }[/math]，并随机选择符号 [math]\displaystyle{ \sigma_i\in\{-1,1\} }[/math]；然后令 [math]\displaystyle{ \Pi_{h(i),i}=\sigma_i }[/math]，其他位置为 [math]\displaystyle{ 0 }[/math]。记 [math]\displaystyle{ u_i }[/math] 为 [math]\displaystyle{ U }[/math] 的第 [math]\displaystyle{ i }[/math] 行，视为 [math]\displaystyle{ \mathbb R^d }[/math] 中的列向量。

1. 证明 [math]\displaystyle{ \Pi^\top\Pi-I_n }[/math] 的第 [math]\displaystyle{ (i,j) }[/math] 个元素在 [math]\displaystyle{ i\ne j }[/math] 时等于 [math]\displaystyle{ \mathbf 1_{h(i)=h(j)}\sigma_i\sigma_j }[/math]，在 [math]\displaystyle{ i=j }[/math] 时等于 [math]\displaystyle{ 0 }[/math]。
2. 推出 [math]\displaystyle{ U^\top\Pi^\top\Pi U-I_d=\sum_{i\ne j:h(i)=h(j)}\sigma_i\sigma_j u_i u_j^\top }[/math]。
3. 证明在计算 [math]\displaystyle{ \mathbb E[\|U^\top\Pi^\top\Pi U-I_d\|_F^2] }[/math] 时，随机符号会使所有交叉项的期望为 [math]\displaystyle{ 0 }[/math]。也就是说，只有同一对 [math]\displaystyle{ (i,j) }[/math] 与自身相乘的项会保留下来。
4. 证明 [math]\displaystyle{ \mathbb E[\|U^\top\Pi^\top\Pi U-I_d\|_F^2]\le \frac{1}{m}\sum_{i\ne j}|u_i|_2^2|u_j|_2^2 }[/math]。
5. 使用 [math]\displaystyle{ \sum_i|u_i|_2^2=|U|_F^2=d }[/math]，证明 [math]\displaystyle{ \mathbb E[|U^\top\Pi^\top\Pi U-I_d|_F^2]\le d^2/m }[/math]。
6. 用 Markov 不等式证明，如果 [math]\displaystyle{ m\ge d^2/(\epsilon^2\delta) }[/math]，那么以概率至少 [math]\displaystyle{ 1-\delta }[/math]，有 [math]\displaystyle{ \|U^\top\Pi^\top\Pi U-I_d\|_F\le \epsilon }[/math]。
7. 证明如果 [math]\displaystyle{ \|U^\top\Pi^\top\Pi U-I_d\|_2\le \epsilon }[/math]，那么对所有 [math]\displaystyle{ x\in\mathbb R^d }[/math] 都有 [math]\displaystyle{ (1-\epsilon)\|Ux\|_2^2\le \|\Pi Ux\|_2^2\le (1+\epsilon)\|Ux\|_2^2 }[/math]。并解释为什么第 (6) 问中的 Frobenius norm bound 足以推出 spectral norm bound。
8. 总结：说明 CountSketch 虽然每一列只有一个非零元素，但当 [math]\displaystyle{ m=O(d^2/(\epsilon^2\delta)) }[/math] 时，仍然可以作为一个 [math]\displaystyle{ d }[/math] 维子空间的 Oblivious Subspace Embedding。

点容量最大流

在通常的最大流问题中，每条边有容量限制。现在考虑如下变体：图为有向图 [math]\displaystyle{ G=(V,E) }[/math]，源点为 [math]\displaystyle{ s }[/math]，汇点为 [math]\displaystyle{ t }[/math]。每条边的容量均为无穷大，但每个点 [math]\displaystyle{ v\in V }[/math] 有容量限制 [math]\displaystyle{ c_v }[/math]，表示流经该点的总流量不能超过 [math]\displaystyle{ c_v }[/math]。可以假设 [math]\displaystyle{ s }[/math] 和 [math]\displaystyle{ t }[/math] 没有点容量限制，或者它们的点容量为无穷大。

请设计一个多项式时间算法，求从 [math]\displaystyle{ s }[/math] 到 [math]\displaystyle{ t }[/math] 的最大可行流量。请清楚说明你的建图方式，并证明你的算法是正确的。

二分图最大匹配与最小点覆盖的线性规划

令 [math]\displaystyle{ G=(L,R,E) }[/math] 是一个二分图。

请写出最大匹配问题的整数规划，并写出它的线性规划松弛。请进一步写出该线性规划的对偶问题。

请写出最小点覆盖问题的整数规划，并说明它与上述对偶线性规划之间的关系。

最后，请利用线性规划对偶性以及二分图匹配问题的整数性，证明二分图中的最大匹配大小等于最小点覆盖大小。也就是说，证明 [math]\displaystyle{ \nu(G)=\tau(G) }[/math]，其中 [math]\displaystyle{ \nu(G) }[/math] 表示最大匹配大小，[math]\displaystyle{ \tau(G) }[/math] 表示最小点覆盖大小。

背包问题的线性规划松弛与取整

考虑 [math]\displaystyle{ 0 }[/math]-[math]\displaystyle{ 1 }[/math] 背包问题。有 [math]\displaystyle{ n }[/math] 个物品，第 [math]\displaystyle{ i }[/math] 个物品的价值为 [math]\displaystyle{ v_i }[/math]，重量为 [math]\displaystyle{ w_i }[/math]，背包容量为 [math]\displaystyle{ C }[/math]。目标是在总重量不超过 [math]\displaystyle{ C }[/math] 的前提下最大化总价值。

请写出该问题的整数规划，并写出它的线性规划松弛。

请设计一个基于线性规划松弛最优解的取整算法，得到一个整数可行解。请证明你的算法的近似比。也就是说，请证明你的算法得到的解的价值至少是最优整数解价值的某个常数比例。

带下界的可行流

给定一个有向网络 [math]\displaystyle{ G=(V,E) }[/math]。每条边 [math]\displaystyle{ e\in E }[/math] 有流量下界 [math]\displaystyle{ \ell_e }[/math] 和流量上界 [math]\displaystyle{ u_e }[/math]，其中 [math]\displaystyle{ 0\le \ell_e\le u_e }[/math]。我们希望判断是否存在一个流 [math]\displaystyle{ f }[/math]，使得每条边都满足 [math]\displaystyle{ \ell_e\le f_e\le u_e }[/math]，并且每个点都满足流量守恒。

请设计一个多项式时间算法判断这样的可行流是否存在。如果存在，请说明如何构造一个可行流。请证明你的算法是正确的。

DAG 最小路径覆盖

给定一个有向无环图 [math]\displaystyle{ G=(V,E) }[/math]。一个路径覆盖是若干条有向路径的集合，使得每个点 [math]\displaystyle{ v\in V }[/math] 恰好出现在其中一条路径中。路径可以只包含单个点。

请设计一个多项式时间算法，求 [math]\displaystyle{ G }[/math] 的最小路径覆盖大小。

请将该问题归约为二分图最大匹配问题。设归约后得到的二分图的最大匹配大小为 [math]\displaystyle{ M }[/math]，请证明原图的最小路径覆盖大小为 [math]\displaystyle{ |V|-M }[/math]。

点不相交路径

给定一个有向图 [math]\displaystyle{ G=(V,E) }[/math] 和两个不同的点 [math]\displaystyle{ s,t\in V }[/math]。我们希望找到尽可能多条从 [math]\displaystyle{ s }[/math] 到 [math]\displaystyle{ t }[/math] 的路径，使得任意两条路径除了端点 [math]\displaystyle{ s }[/math] 和 [math]\displaystyle{ t }[/math] 以外不共享任何内部点。

请设计一个多项式时间算法，求最多有多少条两两内部点不相交的 [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] 路径。请证明你的算法是正确的。

带权点覆盖的 Primal-Dual 算法

给定一个无向图 [math]\displaystyle{ G=(V,E) }[/math]，每个点 [math]\displaystyle{ v\in V }[/math] 有非负权重 [math]\displaystyle{ w_v }[/math]。带权点覆盖问题要求选择一个点集 [math]\displaystyle{ C\subseteq V }[/math]，使得每条边至少有一个端点属于 [math]\displaystyle{ C }[/math]，并最小化 [math]\displaystyle{ \sum_{v\in C} w_v }[/math]。

请写出该问题的整数规划和线性规划松弛。请写出该线性规划松弛的对偶问题。

请基于 primal-dual schema 设计一个 [math]\displaystyle{ 2 }[/math]-approximation 算法，并证明其近似比。你的证明应当说明算法构造的对偶解为什么可行，以及输出的点覆盖的权重为什么至多为对偶目标值的 [math]\displaystyle{ 2 }[/math] 倍。

Set Cover 的线性规划松弛与随机取整

给定一个全集 [math]\displaystyle{ U }[/math] 和集合族 [math]\displaystyle{ \mathcal S }[/math]，其中每个集合 [math]\displaystyle{ S\in\mathcal S }[/math] 有非负成本 [math]\displaystyle{ c_S }[/math]。Set Cover 问题要求选择若干集合，使得 [math]\displaystyle{ U }[/math] 中每个元素都被至少一个被选集合覆盖，并最小化被选集合的总成本。

请写出 Set Cover 的整数规划和线性规划松弛。设线性规划松弛的最优解为 [math]\displaystyle{ x_S }[/math]。

考虑如下随机取整算法：令 [math]\displaystyle{ \alpha\gt 0 }[/math]，并对每个集合 [math]\displaystyle{ S\in\mathcal S }[/math]，独立地以概率 [math]\displaystyle{ x'_S=\min\{1,\alpha x_S\} }[/math] 选择集合 [math]\displaystyle{ S }[/math]。

请证明当 [math]\displaystyle{ \alpha=\Theta(\log |U|) }[/math] 时，所有元素以高概率都被覆盖。请进一步分析该算法的期望成本，并证明它给出一个 [math]\displaystyle{ O(\log |U|) }[/math]-approximation。

带点容量和需求的最小费用运输问题

有若干工厂、仓库和商店。工厂可以生产货物，商店有固定需求，货物可以通过若干运输边从工厂经过仓库运送到商店。每条运输边 [math]\displaystyle{ e }[/math] 有容量上界 [math]\displaystyle{ u_e }[/math] 和单位运输费用 [math]\displaystyle{ a_e }[/math]。每个仓库 [math]\displaystyle{ v }[/math] 有吞吐能力限制 [math]\displaystyle{ c_v }[/math]，表示通过该仓库的总货物流量不能超过 [math]\displaystyle{ c_v }[/math]。每个工厂 [math]\displaystyle{ i }[/math] 的供应上限为 [math]\displaystyle{ s_i }[/math]，每个商店 [math]\displaystyle{ j }[/math] 的需求量为 [math]\displaystyle{ d_j }[/math]。

请设计一个最小费用流模型，判断是否存在满足所有商店需求的运输方案，并在存在时求出最小总运输成本。请说明如何在网络中表示工厂供应、商店需求、运输边容量与费用，以及仓库的点容量限制。请证明你的模型与原问题等价。