近似算法PDF电子书下载

1 引言 1

1.1 确定OPT的下界 2

1.1.1　基数顶点覆盖的近似算法 2

1.1.2　能够改进近似保证吗？ 3

1.2　有好刻画的问题和最小最大关系 4

1.3　练习 6

1.4　注释 8

第一部分 组合算法 13

2 集合覆盖 13

2.1　贪婪算法 13

2.2　分层 15

2.3　应用于最短超字符串 17

2.4　练习 20

2.5　注释 23

3　施泰纳树和旅行商 25

3.1　度量施泰纳树 25

3.1.1　基于最小生成树的算法 26

3.2　度量旅行商 27

3.2.1　简单的因子2算法 28

3.2.2　改进因子到3/2 29

3.3　练习 31

3.4　注释 34

4 多向割和k-割 35

4.1 多向割问题 35

4.2　最小k-割问题 37

4.3　练习 39

4.4　注释 42

5 k-中心 43

5.1　参数修剪应用于度量k-中心 43

5.2　加权形式 45

5.3　练习 47

5.4　注释 48

6　反馈顶点集 49

6.1　圈加权图 49

6.2　分层应用于反馈顶点集 52

6.3　练习 54

6.4　注释 55

7　最短超字符串 57

7.1　因子4算法 57

7.2　改进到因子3 60

7.2.1　达到最优压缩的一半 61

7.3　练习 62

7.4　注释 62

8 背包 63

8.1　背包的伪多项式时间算法 63

8.2 背包的FPTAS 64

8.3 强NP-难解性和FPTAS的存在性 65

8.3.1　FPTAS是最值得找的近似算法吗？ 66

8.4　练习 67

8.5　注释 67

9 装箱问题 69

9.1　渐近PTAS 70

9.2　练习 71

9.3　注释 72

10 最小时间跨度排序 73

10.1　因子2算法 73

10.2 最小时间跨度的PTAS 74

10.2.1　物体大小的种类固定的装箱问题 75

10.2.2　时间跨度问题归约到受限制的装箱问题 75

10.3　练习 76

10.4　注释 77

11 欧几里得旅行商 79

11.1　算法 79

11.2　正确性证明 81

11.3　练习 83

11.4　注释 84

第二部分 基于线性规划的算法 87

12　线性规划对偶介绍 87

12.1　线性规划对偶定理 87

12.2　最小最大关系和线性规划对偶 91

12.3　两个基本的算法设计技术 93

12.3.1　两个技术的比较和整间隙的概念 94

12.4　练习 95

12.5　注释 99

13 用对偶拟合分析集合覆盖 101

13.1　对贪婪集合覆盖算法进行基于对偶拟合的分析 101

13.1.1　能改进这个近似保证吗？ 103

13.2　集合覆盖的推广 104

13.2.1　对偶拟合应用于有约束的集合多次覆盖 105

13.3　练习 108

13.4　注释 109

14 舍入应用于集合覆盖 111

14.1　简单的舍入算法 111

14.2　随机舍入 112

14.3　顶点覆盖的半整性 113

14.4　练习 115

14.5　注释 115

15 对集合覆盖使用原始对偶模式 117

15.1　模式概述 117

15.2　对集合覆盖使用原始对偶模式 119

15.3　练习 121

15.4　注释 121

16　最大可满足性 123

16.1　处理大子句 123

16.2　使用条件期望方法来去随机化 124

16.3　使用线性规划舍入来处理小子句 125

16.4　3/4因子算法 127

16.5　练习 129

16.6　注释 129

17　无关平行机排序 131

17.1　线性规划背景下的参数修剪 131

17.2　极点解的性质 132

17.3　算法 133

17.4　极点解的附加性质 133

17.5　练习 135

17.6　注释 135

18 树的多割和树的整数多商品流 137

18.1 问题和它们的线性规划松弛 137

18.2　基于原始对偶模式的算法 139

18.3　练习 142

18.4　注释 143

19 多向割 145

19.1　令人感兴趣的线性规划松弛 145

19.2　随机舍入算法 147

19.3　结点多向割的半整性 149

19.4　练习 152

19.5　注释 155

20 一般图的多割 157

20.1　和多商品流 157

20.2　基于线性规划舍入的算法 158

20.2.1　增长区域：连续过程 159

20.2.2　离散过程 161

20.2.3　找相继区域 161

20.3　紧例子 163

20.4　多割的一些应用 164

20.5　练习 165

20.6　注释 167

21 最稀疏割 169

21.1　需求多商品流 169

21.2　线性规划模型 170

21.3　度量，割填装和？1-可嵌入性 172

21.3.1　度量的割填装 172

21.3.2　度量的？1-可嵌入性 173

21.4　度量的低失真？1-嵌入 175

21.4.1　确保不过度缩短单独的边 175

21.4.2　确保不过度缩短边 178

21.5　基于线性规划舍入的算法 178

21.6　应用 179

21.6.1　边扩展 179

21.6.2　传导率 180

21.6.3　平衡割 180

21.6.4　最小割线性排列 181

21.7　练习 182

21.8　注释 184

22　施泰纳森林 185

22.1　线性规划松弛和对偶 185

22.2　同步原始对偶模式 186

22.3　分析 190

22.4　练习 192

22.5　注释 197

23　施泰纳网络 199

23.1　线性规划松弛和半整性 199

23.2　迭代舍入技术 202

23.3　刻画极点解 204

23.4　计数论证 206

23.5　练习 208

23.6　注释 214

24　设施定位 217

24.1　对偶的直观理解 218

24.2　松弛原始互补松弛条件 219

24.3　基于原始对偶模式的算法 219

24.4　分析 221

24.4.1　运行时间 222

24.4.2　紧例子 223

24.5　练习 223

24.6　注释 226

25　k-中位点 227

25.1　线性规划松弛和对偶 227

25.2　高级想法 228

25.3　随机舍入 230

25.3.1　去随机化 232

25.3.2　运行时间 232

25.3.3　紧例子 233

25.3.4　整间隙 233

25.4　近似算法的拉格朗日松弛技术 234

25.5　练习 234

25.6　注释 237

26　半定规划 239

26.1　严格二次规划和向量规划 239

26.2　半正定矩阵的性质 240

26.3　半定规划问题 242

26.4　随机舍入算法 243

26.5　对MAX-2SAT改进近似保证 246

26.6　练习 248

26.7　注释 250

第三部分 其他主题 255

27 最短向量 255

27.1　基、行列式和正交性亏量 256

27.2　欧几里得算法和高斯算法 258

27.3　使用格拉姆-施密特正交化确定OPT的下界 259

27.4　推广到n维空间 261

27.5　对偶格和它的算法应用 265

27.6　练习 268

27.7　注释 272

28 计数问题 273

28.1　计数DNF解 274

28.2　网络可靠性 276

28.2.1　确定接近最小割的数目的上界 276

28.2.2　分析 278

28.3　练习 279

28.4　注释 282

29　近似困难性 283

29.1 归约、间隙和困难性因子 283

29.2　PCP定理 285

29.3　MAX-3SAT的困难性 288

29.4　变量出现次数有限的MAX-3SAT的困难性 289

29.5　顶点覆盖和施泰纳树的困难性 291

29.6　团的困难性 293

29.7　集合覆盖的困难性 296

29.7.1　NP的两个证明者一轮刻画 297

29.7.2　配件 298

29.7.3　通过平行重复减小误差概率 299

29.7.4　归约 300

29.8　练习 303

29.9　注释 305

30　未解决的问题 307

30.1　有常数因子算法的问题 307

30.2　其他最优化问题 309

30.3　计数问题 310

30.4　注释 314

附录 317

A 为算法设计者概述复杂性理论 317

A.1 证据和NP类 317

A.2 归约和NP-完全性 318

A.3　NP-最优化问题和近似算法 319

A.3.1　保持近似因子的归约 320

A.4　随机复杂类 321

A.5 自可归约性 322

A.6　注释 324

B 概率论的基本事实 325

B.1　期望和矩 325

B.2　均值偏差 326

B.3　基本分布 327

B.4　注释 327

参考文献 329

问题索引 355

主题索引 359