TSP 问题
2 - 近似的做法：求出最小生成树，按 dfs 序来跑就可以了。2 近似的原因是答案 OPT MST，而按 dfs 序来跑不会超过 MST 的两倍
1.5 - 近似的做法：最小生成树上奇数度数的节点做匹配。1.5 近似的原因是最小匹配 OPT（考虑把所有点都拿来匹配）
平面图 近似《Nearly Linear Time Approximation Schemes for Euclidean TSP and other Geometric Problems》
Maxcut 最大割问题：随机分点，割的期望是 OPT
用硬币生成实数概率：硬币生成一个 的概率，将 二进制表示，若生成的 就继续，< 则输出 0，> 输出 1，期望次数仍是线性
Hash 方法
负载均衡问题：使用 Consistent Hash，有 个请求要分配到 个服务器，我们已经分配好了。现在变成了 个服务器，我们要尽量快速得重新分配且尽量均匀。同理，变成 个请求我们也要快速分配。
做法：维护一个环， 个请求和 个服务器全部 Hash 到环上，每个请求由它后面第一个服务器处理。这样新加服务器就只需要对之前一段重新分配。当然，每个服务器可以在环上随机选 个点。
Point Query 问题：输入 个数，最后询问一个 的出现次数，小空间，要求以大概率满足 ，且只需要 的时间。
做法：维护一个大小 的桶，每个数 Hash 到一个桶， 直接取桶中的和，分析得到 。通过 Markov 的分析：， 取 即有 的概率对，做 次（一起做）就有 的概率对。
K-Heavy Hitter：给一个数据流， 个元素，要求出出现次数 的元素，数据流只给一遍。（要求返回的数出现次数 次即可）
做法：动态维护上面的 Point Query，每次插入 的时候查一下，如果 就插入，否则删除。（由于值域大，所以不好最后再查）
Universal Hash：设计一个 Hash: ，使得
假设 是素数， ，其中 在 随机， 为 进制表示
证明：。虽然 不是随机，但是足够做 Point Query
Bloom Filter：插入删除，询问在不在集合， 空间， 时间，以 的概率成功
维护一个数组，插入一个 直接把 个 设为 1，设数组长度为 ，则考虑所有 ，把 的 某个位置都干掉的概率是 ，全部干掉的概率为 ，取 即可。
Jaccard Similarity：
MinHash： 求 ，claim : 。大概需要做 次
Cosine Similarity：两个向量的 Similarity 定义为 。
问题：给定向量 ，找 Similarity 最高的向量。
SimHash
随机生成一个 ，对于向量 ，定义 。claim : 。那么我们可以用 来估算夹角。问题就变成了找 Hamming 空间最近邻查询。
Hamming 空间最近临查询：给定 ，可以在 求出 最近邻。
做法：设 ，随机 个排列 ，对每个排列，二分找到距离 最近的两个（即 LCP 最大的两个）
求与 最大的 ，仍然使用 minhash，再把 hash 值映到 ，，转换为 Hamming 最近点
欧式空间问题与方法
求 维点集直径： 个点，
随便取一个点求其最远点即为 近邻，设这个值为
作 ，切成 的小方块，把每个点移到方块中心，每个点最多移动 ，所以直接用这个求直径，差别不到 ，复杂度 ，由于所有点都在 的网格内，而 ，故 。后面的 是排序去重。
Quad tree 四分树：不断切，每层切成 个，切到没有点
时空复杂度
欧式空间最近邻查询：
求 最近邻，存在单次询问 时间的做法，只需要在四分树上剪枝即可。
剪枝：， 是格子 中随便选的代表点
性质：若 ，则会被剪枝。（感性理解就是 太小，怎么挪都差不多），具体而言
于是就只有 的方格 会被考虑到
claims: ，若 claims 成立，则只会考虑 个方格。验证 claims，若 $r\le (1+\epsilon)r^{}diam(w)>\epsilon/2r^{}r\le r^{}+diam(w)$ 可知。
WSPD
一个 - WSPD 是一系列的 ，使得 ，且
基于四分树的 WSPD:
1
2
3
4
5
| WSPD (u, v) :
if(u = v & diam(u) = 0) return
if(diam(u) < diam(v)) swap(u, v)
if(diam(u) <= epsilon * dist(u, v)) return {(u, v)}
return merge(WSPD(ui, v))
|
结论：WSPD 会输出 个 。对每个方格 考虑所有 ，有 。（这是因为大了就不会向下递归）。固定 ，那么 中的 只会有 个，而 的可能取值只有两种（递归大的）。 故结论成立。
应用
求精确平面最近点对：求一个 的 WSPD， 中最近的那一对即为答案。
求近似直径：求一个 的 WSPD
Spanner：考虑一个点集 和一个 的完全图，要求保留尽量少的边 ，使得 。求一个 - WSPD，对每个 找到 连边，共 条边。证明略。
MST，欧式最小生成树：在 Spanner 上做最小生成树即可，也是 近似的。
利用随机平移的四分树构造 Tree embedding：将 从 映射到一颗树 上，其中 ，要求 且 。假设从下至上第 层的点直径为 ，第 层向下连边权 的边。有 。分析即考虑枚举 的 LCA，
降维方法
JL （Johnson Linderstrauss Transform）
从 ，保证 个点对之间的距离误差不超过 ， 。
为 是紧的：可以用假设维数可以更低，有些有下界的算法会有更好的结果来卡。
假设 个点为 设 ，那么降为后的距离 ，那么就有 。
JL：考虑一对点 ，，我们考虑构造一个随机映射 ，使得 ，然后多次随机取平均。
随机生成一个 为向量 ，每一维在 中随机，，容易发现满足上述条件
假设向量取 维，那么就构造出映射
核心结论： ，用 Union Bound，即要求 ，于是 。（简易版本直接在 中随机）
JL 优化最小二乘
最小二乘法：，最优解为 ，，复杂度
我们能否用一个 JL 矩阵 ，得到 维的 和 ，使得
注意到这里不能使用 Union Bound（因为不是有限个向量要卡）
一种优秀的做法可以做到 使得 ，其中 是 的 维子空间。之后的复杂度可以降到 ，但是矩阵乘法是 的，所以还需要优化。
一种优秀的方法可以用 代替，其中 每列只有随机一个元素非 0，这个元素是 随机，取 可以代替 JL 矩阵，这样矩阵乘法就降成 了。
证明： - NET：在单位球上选若干个点 ，使得任意 都能找到在 中，距离 的点，选 个点即可。此时任意 可以表示为 ，且满足 ，那么
PCA：（principle, components） 个 维数据点 ，想要找到 个 维基 ，使得每个 可以近似表示为
我们考虑设置优化条件为 （这里 正交，这样 就是 在 上投影的长度（的平方））
应用： 取 DNA， 取 2，与地图重合；Eigen Face，用 维来拟合一张脸。
局限：要求数据有线性特征
求解： 时，容易发现要最大化 ，设 ，那么我们知道 存在正交 使得 ，那么取 即 取 的第一列即可， 的情况，取 的前 列即可。
近似求 Top Principle Componente：考虑一直乘 ，这样拉伸得最长的那一维会一直拉。若假设长轴比其他轴长，那么随机选一个 ，反复应用 ，则最后 会贴近 的方向。
算法：，若 则 break，返回 即可。
claim：随机 ，有常熟概率 ，要求 的误差，只需要
有结论 的概率 常数。常数概率有 ，于是
找第二大： 然后再找最大
SVD 可以来解 PCA，SVD 是最好的 low rank approximation，即最好的 表示秩为 的最佳近似，
CUR 分解 CUR矩阵分解 (对比SVD) - 知乎 (zhihu.com)
压缩感知
我们有 个 “测量” ，信号 测出 个值 ，我们希望从 中恢复出
压缩感知定理
设 其中 且 的每个元素从 中随机采样，则 以高概率，同时对所以 维的 - 稀疏的 ，通过观测 而精确恢复出 。
将恢复问题变成线性规划问题： 直接用单纯形。
Sparse recovery 与数据流方法
Sparse recovry：频数向量 若满足 ，我们可以全部将其恢复出来。其中 。
应用：数据流上做 直径，我们需要猜测一个 ，然后用 来划分格子，若 ，那么我们非空的节点最多就 个。我们猜测 ，对每一个 使用一个 的 Sparse recovery，找到满足条件最小的 。
1 - sparse recovery：维护 c_1，计算出 后 check 即可
k - sparse recovery：维护 个 的 Hash，每个桶维护一个 1 - sparse recovery
采样
返回 上的均匀采样
个物品的盲盒，采样 次就可以带概率凑齐 种，因此对于 k - sparse 数据流，只需要独立运行 次 采样就可以恢复。
随机采样实现：设计 使得 ，插入 时，若 那么插入 ，最后找到任意一个 1 - sparse 的 返回即可
应用：图数据流上求联通分量，空间
类似 Bruvka，查询的时候每一轮，对每个联通分量 找到一条跨越边然后合并，我们需要用较少的空间找到跨越边。设计 采样，定义频数向量为
那么 的 只含有跨越 的边
图数据流最小生成树，存在空间 的 近似
对每种边权维护上述的 ，边权可以向上取到 的幂，这样只有 种边权
