高级算法 (Spring 2025)/作业二

• 每道题目的解答都要有完整的解题过程，中英文不限。
• 我们推荐大家使用LaTeX, markdown等对作业进行排版。
• 没有条件的同学可以用纸笔完成作业之后拍照。

1. 课程中介绍的 tabulation hashing 被称为 simple tabulation hashing。 tabulation hashing 还有不少别的扩展和强化。尝试调查并介绍其中一些，并尝试解释该 tabulation hashing 克服了其他 tabulation hashing 的什么问题，有什么优点和缺点，尝试解释为什么。你也可以调查一个你喜欢的哈希函数。你的分数取决于你的解释的详细程度和准确程度。
2. 考虑使用 Johnson-Lindenstrauss Transformation 对某个单位向量进行降维。如果我们保证该单位向量具有较低的 [math]\displaystyle{ \ell_\infty }[/math]-norm，即对于单位向量 [math]\displaystyle{ \mathbf x\in\mathbb S^{d-1} }[/math] 保证 [math]\displaystyle{ \max_i\mathbf x_i }[/math] 较低，我们可以在保证正确性的前提下降到更低的维数吗？可以降低到多少维？你的答案应该包含 [math]\displaystyle{ d,\epsilon,\delta,\ell_\infty }[/math] 四个参数。尝试证明你的结论。
3. LSH 函数的设计宗旨是尽量使得相邻的点容易碰撞的同时，相距较远的点不容易碰撞。我们可以反过来想象“被放入某一个桶中的数据点的集合”。这个集合是随机的，在课程中介绍的LSH中，这样的集合是一个随机的Hamming cube。从这个角度考虑的话，不严格地说，我们可以想象，“如果一个数据点被放入了这样一个随机的集合中，当这样的集合是什么形状的时候，相邻的数据点比较容易也在这个集合中，而较远的数据点不容易在这个集合中”。
   1. 考虑 metric space [math]\displaystyle{ ([0,n]^d,\mathrm{d}) }[/math] 。 [math]\displaystyle{ \mathrm{d}(x,y)=\sqrt{\sum_i (\min\{|x_i-y_i|,n-|x_i-y_i|\})^2} }[/math]。（想象在每个维度上都“绕回”，即 [math]\displaystyle{ (0,0,0,\dots) }[/math] 和 [math]\displaystyle{ (n,n,n,\dots) }[/math] 的距离是 [math]\displaystyle{ 0 }[/math]。）对于这样的 metric space 你会如何设计 LSH 函数？尝试解释为什么。
   2. 再考虑球面空间 [math]\displaystyle{ (\mathbb S^{d-1},\mathrm{d}) }[/math]，其中 [math]\displaystyle{ \mathrm{d}(x,y)=\arccos\langle x,y\rangle }[/math]（即所有点都是单位向量，我们用两个向量的夹角角度表示向量之间的距离）。对于这样的 metric space 你会如何设计 LSH 函数？尝试解释为什么。
4. 假设 [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] 个球中不会有两个球被丢进了同一个桶中）。
5. 点容量问题：现在我们的网络流问题中，每条边的容量是无穷大，但是流经每个节点 [math]\displaystyle{ i }[/math] 有容量限制 [math]\displaystyle{ c_i }[/math]。设计一个求解该模型的最大流的算法，尝试解释其正确性。
6. 某工厂生产产品需 [math]\displaystyle{ k }[/math] 种零件。供应商有 [math]\displaystyle{ m }[/math] 家，第 [math]\displaystyle{ i\in[m] }[/math] 家提供零件 [math]\displaystyle{ j\in[k] }[/math] 的价格为 [math]\displaystyle{ a_{ij} }[/math]，且最多供应 [math]\displaystyle{ c_{ij} }[/math] 个。工厂每天需零件 [math]\displaystyle{ j\in[k] }[/math] 的数量为 [math]\displaystyle{ d_j }[/math]。设计一个算法求解最小化总采购成本，尝试解释其正确性。
7. Let [math]\displaystyle{ G = (L, R, E) }[/math] be a bipartite graph. Write down the linear program that finds the maximum matching in [math]\displaystyle{ G }[/math], and the linear program that finds the minimum vertex cover of [math]\displaystyle{ G }[/math]. Prove that the size of the maximum matching in [math]\displaystyle{ G }[/math] is equal to the size of the minimum vertex cover in [math]\displaystyle{ G }[/math]. This suggests that the vertex cover problem in bipartite graphs is polynomial time solvable.
8. 考虑 0-1 背包问题：有 [math]\displaystyle{ n }[/math] 个物品，第 [math]\displaystyle{ i }[/math] 个物品的价值和重量分别是 [math]\displaystyle{ v_i,w_i }[/math]，背包容量 [math]\displaystyle{ C }[/math]. 请写出对应的整数规划，和它的线性规划松弛。设计一个根据松弛线性规划最优解取整以取得优秀整数可行解的方案，并尝试分析你的答案与最优解的近似比。