算法分析進階：超越最壞情況分析 Beyond the Worst-Case Analysis of Algorithms

譯者序
前言
作者名單
第1章 引言
1.1 演算法最壞的情況分析
1.1.1 不可比較演算法的比較
1.1.2 最壞情況分析帶來的好處
1.1.3 演算法分析的目標
1.2 著名的失敗事件和對替代方法的迫切需要
1.2.1 線性規劃的單純形法
1.2.2 聚類與NP困難最最佳化問題
1.2.3 機器學習的不合理的有效性
1.2.4 線上演算法分析
1.2.5 最壞情況分析的騙局
1.3 範例：線上分頁問題中的參數化界
1.3.1 根據引用局部性的參數化
1.3.2 定理1.1的證明
1.3.3 討論
1.4 本書概述
1.4.1 最壞情況分析的改進
1.4.2 確定性資料模型
1.4.3 半隨機模型
1.4.4 平滑分析
1.4.5 機器學習和統計學中的應用
1.4.6 進一步的應用
1.5 本章註解
致謝
參考文獻
練習題
第一部分 最壞情況分析的改進
第2章 參數化演算法
2.1 引言
2.1.1 熱身：頂點覆蓋問題
2.2 隨機化
2.2.1 隨機分離：集合拆分問題
2.2.2 去隨機化
2.3 結構上的參數化
2.4 核心化
2.4.1 熱身：Buss規則
2.4.2 形式定義以及與FPT的成員關係
2.4.3 Buss規則在矩陣秩上的推廣
2.5 困難性和最優性
2.5.1 W[1]困難性
2.5.2 ETH和SETH
2.5.3 核心化的困難性和最適性
2.6 展望：新的範例與應用領域
2.6.1 FPT-近似和有損核心
2.6.2 P問題中的FPT
2.6.3 應用領域
2.7 總體方向
2.8 本章註解
參考文獻
練習題
第3章 從自適應分析到實例最適性
3.1 個案研究1：最大點集合問題
……
第二部分 確定性資料模型
第三部分 半隨機模型
第四部分 平滑分析
第五部分 機器學習與統計學的應用
第六部分 進一步的應用