近似算法PDF电子书下载
- 电子书积分:13 积分如何计算积分?
- 作 者:(美)Vijay V.Vazirani著
- 出 版 社:北京:高等教育出版社
- 出版年份:2010
- ISBN:9787040298635
- 页数:363 页
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
- 《计算机视觉系统设计及显著性算法研究》徐海波著 2019
- 《全局光照算法技术》(美)菲利普·特瑞(Philip Dutre)等著 2019
- 《RNA折叠结构预测算法与计算复杂性》刘振栋著 2019
- 《ROS机器人编程与SLAM算法解析指南》陶满礼 2020
- 《图解数据结构与算法》汪建 2020
- 《信息融合中估计算法的性能评估》毛艳慧著 2019
- 《基于群体智能优化算法的文本过滤关键技术研究》朱振方,刘培玉,尉永清著 2019
- 《被算法操控的生活:重新定义精准广告、大数据和AI=OUTNUMBERED FROM FACEBOOK AND GOOGLE TO FAKE NEWS AND FILTER-BUBBL》(瑞典)大卫·萨普特(DavidSumpter) 2020
- 《海洋动力环境模拟数值算法及应用》王永学 2019
- 《机器视觉算法原理与编程实战》杨青著 2019
- 《全国高等中医药行业“十三五”创新教材 中医药学概论》翟华强 2019
- 《培智学校义务教育实验教科书教师教学用书 生活适应 二年级 上》人民教育出版社,课程教材研究所,特殊教育课程教材研究中心编著 2019
- 《指向核心素养 北京十一学校名师教学设计 英语 七年级 上 配人教版》周志英总主编 2019
- 《习近平总书记教育重要论述讲义》本书编写组 2020
- 《办好人民满意的教育 全国教育满意度调查报告》(中国)中国教育科学研究院 2019
- 《高等数学试题与详解》西安电子科技大学高等数学教学团队 2019
- 《北京生态环境保护》《北京环境保护丛书》编委会编著 2018
- 《教育学考研应试宝典》徐影主编 2019
- 《语文教育教学实践探索》陈德收 2018
- 《家庭音乐素养教育》刘畅 2018