你的进度
0/ 34 节已标记完成
下一节: 最大割的局部搜索
完成记录保存在此浏览器中。
这门课在网上
CSCI4240 笔记里的内容
数字只算这门课 34 节公开笔记里写了什么,不是网上已记录的关系。目前其中 0 节已细致地记录到网上。
在网上定理卡 74 · 定义 52 · 反例 36 · 概念视角 17 · 证明透视 40
第 1 章 · 1 节
局部搜索
由局部最优性得到近似保证。
- 1.1
最大割的局部搜索
由单顶点局部最优解证明一个近似保证。
第 2 章 · 2 节
零和博弈
混合策略与最优性证书。
- 2.1
有限零和博弈中的混合策略
利用线性规划对偶解释有限博弈中的最优随机化。
- 2.2
多人博弈中的无遗憾策略
利用完全信息乘性权重法构造近似粗相关均衡。
第 3 章 · 4 节
集中不等式
独立指示变量的乘法尾界。
- 3.1
独立指示变量的 Chernoff 界
推导乘性尾界,并将其应用于抽样与稀疏计数。
- 3.2
集中不等式与独立重复
证明马尔可夫和切比雪夫不等式,并分析独立重复。
- 3.3
球入箱问题中的最大负载
利用一阶矩与二阶矩证明最大负载的上界与下界。
- 3.4
生日碰撞与二阶矩
分析碰撞概率,以及其背后的独立性假设。
第 4 章 · 5 节
随机舍入
集合覆盖的随机舍入与修补。
- 4.1
集合覆盖的随机舍入
把分数覆盖转化为可行覆盖,并界定其期望代价。
- 4.2
为什么线性规划对偶是精确的
通过投影不等式并追踪非负证书来证明强对偶性。
- 4.3
集合覆盖:收费、线性松弛与原始—对偶证书
证明调和贪心与频率舍入保证,并在构造覆盖时同步建立可行对偶下界。
- 4.4
度量旅行商问题的近似算法
利用生成树、欧拉(Euler)回路与度量捷径(shortcutting)来界定巡回路线的代价。
- 4.5
背包问题的完全多项式时间近似方案
对利润进行缩放,并求解最小重量动态规划,从而得到明确的近似保证。
第 5 章 · 4 节
随机游走
利用谱界放大成功概率。
- 5.1
随机游走放大
利用绝对谱界限控制对坏集合的重复访问概率。
- 5.2
随机游走与谱混合
利用正则图的特征值界定随机游走的收敛速度。
- 5.3
2-SAT 的随机游走搜索
利用距离势函数,界定随机化可满足赋值搜索的期望时间。
- 5.4
平稳分布与懒惰游走
证明有限马尔可夫(Markov)链平稳分布的存在性,以及基于耦合的收敛结果。
第 6 章 · 7 节
条件期望
以条件期望去随机化 Max-2SAT 保证。
- 6.1
Max-2SAT 与条件期望
把随机赋值的期望转化为确定性保证。
- 6.2
最小割的随机收缩算法
证明随机收缩算法的成功概率,并通过重复运行放大该概率。
- 6.3
通过随机取值进行多项式恒等检验
证明 Schwartz–Zippel 界,并将其应用于二部图完美匹配。
- 6.4
矩阵乘积的随机化验证
利用随机向量以单侧错误验证矩阵乘积。
- 6.5
Lovász 局部引理
证明局部引理,并利用稀疏的依赖关系说明所有坏事件可以同时被避免。
- 6.6
随机割与条件期望
用随机划分证明好割存在,并以条件期望去随机化。
- 6.7
随机赋值与 MAX-SAT 近似
分析带权子句的满足情况,并用条件期望法将随机算法去随机化。
第 7 章 · 6 节
在线决策
滑雪租赁的竞争分析。
- 7.1
在线决策与租滑雪装备问题
证明确定性竞争保证及与之匹配的下界。
- 7.2
在线租买:竞争比与随机购买阈值
比较离散模型与连续时间竞争比,并提供附解练习。
- 7.3
在线分页与竞争分析
分析分页问题中的标记阶段与对抗性请求。
- 7.4
LRU 分页的精确竞争界
利用按访问新近程度加权的势函数,证明最近最少使用(LRU)分页算法是 k-竞争的。
- 7.5
在线分页的随机化标记算法
利用调和和,在不经意对手下界定随机分页算法的期望代价。
- 7.6
同构机器上的列表调度
利用负载下界与最长作业下界,证明一个紧的完工时间保证。
第 8 章 · 1 节
随机覆盖
期望等待时间与高概率覆盖。
- 8.1
集齐种类:期望与尾部界
分析随机停止时间与覆盖尾部界。
第 9 章 · 1 节
数据流抽样
均匀水塘抽样与有限总体估计。
- 9.1
水塘抽样与估计数据流比例
证明未知长度数据流的均匀抽样不变式,并推导有限总体误差界。
第 10 章 · 2 节
哈希与草图
哈希与草图
- 10.1
两两独立的二元哈希
构造一个仿射哈希族,并分析基于碰撞的保证。
- 10.2
用于频率估计的 Count–Min 草图
利用两两独立哈希与独立重复来界定碰撞误差。
第 11 章 · 1 节
半正定规划
半正定规划
- 11.1
最大割向量与随机超平面
推导半正定松弛,证明角度分离概率,并得到精确的期望近似常数。