《组合最优化 算法和复杂性》求取 ⇩

前言1

第一章 最优化问题1

1.1 引言1

1.2 最优化问题4

1.3 领域8

1.4 局部最优与整体最优10

1.5 凸集与凸函数12

1.6 凸规划问题15

习题17

注释与参考资料20

A.1 线性代数21

附录：术语与符号21

A.2 图论22

A3 拟Algol语言27

第二章 单纯形算法30

2.1 线性规划问题的形式30

2.2 基本可行解33

2.3 线性规划的几何39

2.3.1 线性空间和仿射空间39

2.3.2 有界凸多面体40

2.3.3 有界多面体与LP43

2.4 基本可行解的替换49

2.5 单纯形表53

2.6 进入基列的选择55

2.7 旋转元的选择和Bland反循环算法61

2.8 单纯形算法的初始基本可行解68

2.9 旋转变换的几何说明73

习题79

注释与参考资料82

第三章 对偶性86

3.1 一般形式的线性规划的对偶86

3.2 互补松弛性91

3.3 Farkas引理93

3.4 最短路问题及其对偶95

3.5 单纯形表中对偶解的信息100

3.6 对偶单纯形算法102

3.7 对偶单纯形算法的解释104

习题106

注释与参考资料110

第四章 关于单纯形算法的计算讨论112

4.1 修正的单纯形算法112

4.2 修正的单纯形算法在计算上的意义114

4.3 最大流问题及用修正的单纯形方法求其解116

4.4 Dantzig-Wolfe的分解算法122

习题129

注释与参考资料131

5.1 引言132

第五章 原始-对偶算法132

5.2 原始-对偶算法133

5.3 原始-对偶算法的说明137

5.4 最短路问题的原始-对偶算法138

5.5 关于方法思路的说明143

5.6 最大流问题的原始-对偶算法144

习题146

注释与参考资料147

第六章 最大流和最短路的原始-对偶算法：Ford-Fulkerson算法和Dijkstra算法148

6.1 最大流最小截定理148

6.2 Ford和Fulkerson标号算法152

6.3 标号算法的有限性问题153

6.4 Dijkstra算法161

6.5 Floyd-Warshall算法163

习题167

注释与参考资料170

第七章 最小费用流的原始-对偶算法172

7.1 最小费用流问题172

7.2 组合化容量-圈算法173

7.3 组合化费用-迭加算法177

7.4 Hitchcock问题的原始-对偶算法-αβ算法179

7.5 最小费用流问题变换为Hitchcock问题185

7.6 结束语189

习题190

注释与参考资料192

第八章 算法与复杂性198

8.1 可计算性198

8.2 时间界199

8.3 例子的规模202

8.4 算法分析206

8.5 多项式时间算法207

8.6 单纯形算法不是多项式时间的算法210

8.7 椭球算法216

8.7.1 LP，LI和LSI216

8.7.2 仿射变换与椭球221

8.7.3 算法223

8.7.4 算法的精度230

习题235

注释与参考资料241

第九章 最大流问题的有效算法248

9.1 图的搜索248

9.2 标号算法的病症是什么254

9.3 网络标号与有向图的搜索258

9.4 一个0(？3)的最大流算法263

9.5 具有单位容量的情况269

习题272

注释与参考资料275

第十章 匹配算法279

10.1 匹配问题279

10.2 二部图的匹配算法283

10.3 二部图匹配与网络流287

10.4 非二部图的匹配：花289

10.5 非二部图匹配：一个算法298

习题309

注释与参考资料313

第十一章 赋权匹配316

11.1 引言316

11.2 指派问题的匈牙利方法317

11.3 非二部图赋权匹配问题326

11.4 小结341

习题342

注释与参考资料346

第十二章 支撑树与拟阵348

12.1 最小支撑树问题348

12.2 最小支撑树问题的O(？)算法352

12.3 Greedy算法356

12.4 拟阵358

12.5 两个拟阵的交369

12.6.1 赋权拟阵交381

12.6 拟阵交问题的某些推广381

12.6.2 拟阵对382

12.6.3 三个拟阵交383

习题385

注释与参考资料391

第十三章 整数线性规划395

13.1 引言395

13.2 全单位模性质406

13.3 ILP解的上界409

习题416

注释与参考资料417

14.1 Gomory割420

第十四章 整数线性规划的割平面算法420

14.2 字典序429

14.3 分数对偶算法的有限性434

14.4 其它的割平面算法436

习题437

注释与参考资料439

第十五章 NP-完备问题441

15.1 引言441

15.2 一个最优化问题的三种提法442

15.3 P类与NP类447

15.4 多项式时间的归结452

15.5 Cook定理454

15.6 几个NP-完备问题：团与货郎问题461

15.7 另一些NP-完备问题：匹配、覆盖和划分476

习题483

注释与参考资料488

第十六章 再论NP-完备性493

16.1 co-NP类493

16.2 拟多项式算法和“强”NP-完备性497

16.3 NP-完备问题的特例和一般化502

16.3.1 使用限制方法证明NP-完备性503

16.3.2 NP-完备问题的容易特例504

16.3.3 NP-完备问题的困难特例506

16.4.2 NP困难问题509

16.4 一些有关的概念509

16.4.1 多项式时间约化509

16.4.3 非确定的图灵机511

16.4.4 多项式空间完备问题513

16.5 结束语514

习题515

注释与参考资料519

第十七章 近似算法523

17.1 点覆盖的启发式方法：一个例子523

17.2 货郎问题的近似算法527

17.3 近似方法539

17.4 一些否定的结果549

习题554

注释与参考资料555

第十八章 分枝定界和动态规划559

18.1 整数线性规划的分枝定界559

18.2 一般意义下的分枝定界564

18.3 优势关系570

18.4 分枝定界策略571

18.5 应用于流水作业车间时间表问题573

18.6 动态规划578

习题581

注释与参考资料583

19.1 引言586

第十九章 局部寻优法586

19.2 问题1：货郎问题587

19.3 问题2：最小费用残存网络589

19.4 问题3：海底天然气管道系统拓朴结构595

19.5 问题4：均匀图划分599

19.6 局部寻优法的一些普遍性问题604

19.7 局部寻优法的几何608

19.8 一个大的极小精确领域的例子613

19.9 货郎问题的精确局部寻优法的复杂性616

习题621

注释与参考资料624