组合最优化 理论与算法PDF电子书下载

第1章 引言 1

1.1枚举法 2

1.2算法的运行时间 4

1.3线性优化问题 7

1.4整序 8

习题 10

参考文献 10

第2章图 12

2.1基本定义 12

2.2树，圈和截 15

2.3连通性 22

2.4欧拉图和二部图 27

2.5可平面性 30

2.6平面对偶性 36

习题 38

参考文献 41

第3章 线性规划 43

3.1多面体 44

3.2单纯形法 47

3.3单纯形法的执行 50

3.4对偶性 53

3.5凸包和多面体 57

习题 58

参考文献 60

第4章 线性规划算法 62

4.1顶点和面的尺寸 62

4.2连分数 64

4.3高斯消去法 67

4.4椭球法 70

4.5 Khachiyan定理 76

4.6分离和优化 77

习题 83

参考文献 84

第5章 整数规划 86

5.1多胞形的整数闭包 87

5.2单模变换 91

5.3全对偶整性 93

5.4全单模矩阵 96

5.5割平面 100

5.6拉格朗日松弛 104

习题 106

参考文献 109

第6章 支撑树和树形图 111

6.1最小支撑树 111

6.2最小树形图 116

6.3多面体描述 119

6.4储存支撑树和树形图 122

习题 125

参考文献 128

第7章 最短路 131

7.1一个起点的最短路 132

7.2全部点对间的最短路 136

7.3最小平均圈 138

习题 140

参考文献 141

第8章 网络流 144

8.1最大流-最小截定理 145

8.2 Menger定理 148

8.3 Edmonds-Karp算法 150

8.4阻塞流与Fujishige算法 152

8.5 Goldberg-Tarjan算法 154

8.6 Gomory-Hu树 158

8.7无向图的最小容量截 164

习题 166

参考文献 169

第9章 最小费用流 174

9.1问题表述 174

9.2最优性准则 176

9.3最小平均圈消去算法 178

9.4逐次最短路算法 181

9.5 Orlin算法 185

9.6网络单形算法 188

9.7时变流 192

习题 193

参考文献 196

第10章 最大匹配 199

10.1二部图匹配 199

10.2 Tutte矩阵 201

10.3 Tutte定理 203

10.4因子临界图的耳分解 206

10.5 Edmonds匹配算法 210

习题 219

参考文献 222

第11章 加权匹配 225

11.1分配问题 225

11.2加权匹配算法概述 227

11.3加权匹配算法的实现 229

11.4后续优化 241

11.5匹配多面体 242

习题 245

参考文献 246

第12章 b-匹配与T-连接 249

12.1 b-匹配 249

12.2最小权T-连接 252

12.3 T-连接与T截 256

12.4 Padberg-Rao定理 259

习题 261

参考文献 263

第13章 拟阵 265

13.1独立系统与拟阵 265

13.2另外的拟阵公理 268

13.3对偶 273

13.4贪婪算法 276

13.5拟阵交 281

13.6拟阵划分 285

13.7加权拟阵交 286

习题 290

参考文献 292

第 14章 拟阵的推广 294

14.1广义拟阵 294

14.2拟阵多面体 297

14.3求次模函数的最小值 301

14.4 Schrijver算法 303

14.5对称次模函数 307

习题 309

参考文献 310

第15章NP完备性 313

15.1 Turing机 313

15.2 Church的论题 315

15.3 P与NP 320

15.4 Cook定理 324

15.5某些基本的NP完备问题 328

15.6 coNP类 334

15.7 NP难问题 336

习题 339

参考文献 342

第16章 近似算法 344

16.1集覆盖 344

16.2 Max-Cut（最大割）问题 349

16.3着色 355

16.4近似方案 361

16.5最大可满足性 364

16.6 PCP定理 368

16.7 L归约 372

习题 378

参考文献 380

第17章 背包问题 386

17.1分数型背包问题和赋权中位问题 386

17.2伪多项式算法 388

17.3一个全多项式近似方案 390

习题 393

参考文献 393

第18章 装箱问题 395

18.1贪婪算法 395

18.2渐近近似方案 400

18.3 Karmarkar-Karp算法 404

习题 407

参考文献 408

第19章 多商品流和边不重路 410

19.1多商品流 411

19.2多商品流算法 414

19.3有向的边不重路问题 418

19.4无向的边不重路问题 421

习题 426

参考文献 427

第20章 网络设计问题 431

20.1 Steiner树 431

20.2 Robins- Zelikovsky算法 436

20.3可靠网络设计 441

20.4原始对偶近似算法 444

20.5 Jain算法 452

习题 457

参考文献 459

第21章 旅行商问题 463

21.1旅行商问题的近似算法 463

21.2欧氏平面上的旅行商问题 467

21.3局部搜索 474

21.4旅行商多面体 479

21.5下界 484

21.6分枝定界 487

习题 489

参考文献 491

第22章 选址问题 495

22.1无容量限制的设施选址问题 495

22.2基于线性规划的舍入算法 497

22.3原始对偶算法 499

22.4放缩与贪婪增广方法 504

22.5界定设施的数目 507

22.6局部搜索 510

22.7有容量限制的设施选址问题 515

22.8设施选址问题的一般模型 518

习题 524

参考文献 525

名词索引 528

《现代数学译丛》已出版书目 543