你的進度
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
最大割向量與隨機超平面
推導半正定鬆弛,證明角度分離概率,並得到精確的期望近似常數。