算法分析進階：超越最壞情況分析

譯者序
前言
作者名單第1章　引言1　1.1　算法的最壞情況分析1
　　1.1.1　不可比較算法的比較1
　　1.1.2　最壞情況分析帶來的好處2
　　1.1.3　算法分析的目標2
　1.2　著名的失敗事件和對替代方法的
迫切需要3
　　1.2.1　線性規(guī)劃的單純形法3
　　1.2.2　聚類與NP困難最優(yōu)化
問題3
　　1.2.3　機器學(xué)習(xí)的不合理的
有效性4
　　1.2.4　在線算法分析5
　　1.2.5　最壞情況分析的騙局5
　1.3　示例：在線分頁問題中的參數(shù)
化界6
　　1.3.1　根據(jù)引用局部性的參數(shù)化6
　　1.3.2　定理1.1的證明7
　　1.3.3　討論8
　1.4　本書概述9
　　1.4.1　最壞情況分析的改進9
　　1.4.2　確定性數(shù)據(jù)模型10
　　1.4.3　半隨機模型11
　　1.4.4　平滑分析12
　　1.4.5　機器學(xué)習(xí)和統(tǒng)計學(xué)中的
應(yīng)用13
　　1.4.6　進一步的應(yīng)用14
　1.5　本章注解16
　致謝16
　參考文獻16
　練習(xí)題17第一部分　最壞情況分析的改進第2章　參數(shù)化算法20　2.1　引言20
　　2.1.1　熱身：頂點覆蓋問題20
　2.2　隨機化23
　　2.2.1　隨機分離：集合拆分問題25
　　2.2.2　去隨機化26
　2.3　結(jié)構(gòu)上的參數(shù)化26
　2.4　核心化27
　　2.4.1　熱身：Buss規(guī)則27
　　2.4.2　形式定義以及與FPT的成員
關(guān)系28
　　2.4.3　Buss規(guī)則在矩陣秩上的
推廣29
　2.5　困難性和最優(yōu)性30
　　2.5.1　W[1]困難性30
　　2.5.2　ETH和SETH31
　　2.5.3　核心化的困難性和最優(yōu)性32
　2.6　展望：新的范例和應(yīng)用領(lǐng)域33
　　2.6.1　FPT-近似和有損核心33
　　2.6.2　P問題中的FPT35
　　2.6.3　應(yīng)用領(lǐng)域36
　2.7　總體方向36
　2.8　本章注解36
　參考文獻37
　練習(xí)題40第3章　從自適應(yīng)分析到實例
最優(yōu)性41　3.1　案例研究1：最大點集合問題41
　　3.1.1　Jarvis步進算法41
　　3.1.2　Graham掃描算法42
　　3.1.3　Marriage Before Conquest
算法42
　　3.1.4　垂直熵43
　　3.1.5?。ê鲆曧樞虻模嵗?br />最優(yōu)性44
　　3.1.6　部分有序的輸入46
　　3.1.7　不可能性的結(jié)果46
　3.2　案例研究2：實例最優(yōu)的聚合
算法47
　　3.2.1　實例最優(yōu)性47
　　3.2.2　問題的設(shè)定48
　　3.2.3　閾值算法48
　　3.2.4　閾值算法的實例最優(yōu)性49
　　3.2.5　最優(yōu)性比上的匹配下界49
　3.3　對更多結(jié)果和技術(shù)的綜述50
　　3.3.1　輸入順序50
　　3.3.2　輸入結(jié)構(gòu)50
　　3.3.3　順序與結(jié)構(gòu)之間的協(xié)同
作用51
　3.4　討論51
　　3.4.1　與參數(shù)化算法的比較51
　　3.4.2　與在線算法的競爭分析的
比較52
　3.5　開放式問題精選52
　　3.5.1　高維的情況52
　　3.5.2　最大點集合的分層52
　3.6　關(guān)鍵要點53
　3.7　本章注解53
　致謝53
　參考文獻53
　練習(xí)題54第4章　資源增廣57　4.1　再論在線分頁問題57
　　4.1.1　模型57
　　4.1.2　FIF和LRU57
　　4.1.3　競爭比58
　　4.1.4　資源增廣界58
　4.2　討論59
　4.3　自私路由問題61
　　4.3.1　模型和一個推動研究的
示例61
　　4.3.2　資源增廣保證62
　　4.3.3　定理4.4的證明
（平行邊）62
　　4.3.4　定理4.4的證明
（一般網(wǎng)絡(luò)）63
　4.4　調(diào)度問題中速度的改變64
　　4.4.1　非預(yù)知未來調(diào)度64
　　4.4.2　關(guān)于SETF的資源增廣
保證65
　　4.4.3　引理4.8的證明：準備
工作66
　　4.4.4　引理4.8的證明：主要
論證67
　4.5　松弛競爭算法69
　4.6　本章注解71
　致謝71
　參考文獻71
　練習(xí)題72第二部分　確定性數(shù)據(jù)模型第5章　擾動彈性76　5.1　引言76
　5.2　組合最優(yōu)化問題78
　5.3　認證算法的設(shè)計80
　5.4　認證算法示例84
　5.5　擾動彈性的聚類問題85
　　5.5.1　度量擾動彈性蘊含了
中心緊鄰性87
　5.6　2-擾動彈性實例的算法88
　5.7　k-median的（3+ε)-認證的
局部搜索算法90
　5.8　本章注解91
　參考文獻92
　練習(xí)題94第6章　近似解穩(wěn)定性與代理
目標95　6.1　引言和動機95
　6.2　定義和討論96
　6.3　k-median問題99
　　6.3.1　定義99
　　6.3.2　一些令人關(guān)注的結(jié)果99
　　6.3.3　算法和證明100
　　6.3.4　小簇的處理104
　6.4　k-means、min-sum以及其他聚類
目標105
　6.5　聚類應(yīng)用105
　6.6　納什均衡106
　6.7　總體方向107
　6.8　開放式問題108
　6.9　松弛108
　6.10　本章注解108
　參考文獻109
　練習(xí)題110第7章　稀疏恢復(fù)111