近似算法【2025|PDF|Epub|mobi|kindle电子书版本百度云盘下载】

近似算法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/229

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　改进到因子360

7.2.1　达到最优压缩的一半61

7.3　练习62

7.4　注释62

8 背包63

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

8.2 背包的FPTAS64

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

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

8.4　练习67

8.5　注释67

9 装箱问题69

9.1　渐近PTAS70

9.2　练习71

9.3　注释72

10 最小时间跨度排序73

10.1　因子2算法73

10.2 最小时间跨度的PTAS74

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