算法分析進(jìn)階：超越最壞情況分析

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