书籍详情

网络流:理论、算法与应用 英文版

网络流:理论、算法与应用 英文版

作者:拉文德拉K.阿胡亚(Ravindra K.Ahuja)等著

出版社:机械工业出版社

出版时间:2005-05-01

ISBN:9787111159193

定价:¥108.00

购买这本书可以去
内容简介
  本书全面介绍了经典的和现代的网络流技术,包括综合的理论、算法与应用。主要内容包括:路径、树与周期,算法设计与分析,最大流与最小流算法,分派与匹配,最小生成树,拉格朗日松弛与网络优化等。书中包含大量练习题,拓展了本书的内容,便于教学。本书特点■深入介绍功能强大的算法策略和分析工具,如数据缩放和势函数变量。■讨论有关网络优化的重要主题及实际解决方案,如拉格朗日松弛法。■包括广泛的文献注解,提供宝贵的历史背景和指导。■包含800多道难度不一的练习题。
作者简介
  RavindraK.Ahuja:印度理工学院坎普尔分校工业与管理工程系副教授。1986年至1988年,他曾在麻省理工学院斯隆管理学院做访问学者,与沃林教授合作研究若干网络流问题的快速算法,这期间的工作促成了本书的面世。他的研究方向为网络流、组合优化、算法的计算测试。ThomasL.Magnanti:麻省理工学院斯隆管理学院管理科学系教授。他曾任美国运筹学会的会长和《OperationsResearch》杂志的主编。他是美国国家工程院院士。他的研究方向为大规模优化,包括网络设计、整数规划及其在通信、制造和交通中的应用。JamesB.Orlin:麻省理工学院斯隆管理学院运筹学教授。从1985年至1990年,他荣膺美国国家自然科学基金会颁发的总统青年学者奖。目前,他的研究方向为网络流、组合优化及物流学。
目录
1  INTRODUCTION, 1
 1.1  Introduction,  1
 1.2  Network Flow Problems, 4
 1.3  Applications, 9
 1.4  Summary,  18
 Reference Notes,  19
 Exercises,  20
 2  PATHS, TREES, AND CYCLES, 28
 2.1  Introduction, 23
 2.2  Notation and Definitions,  24
 2.3  Network Representations,  31
 2.4  Network Transformations, 38
 2.5  Summary, 46
 Reference Notes,  47
 Exercises, 47
 3  ALGORITHM DESIGN AND ANALYSIS,  58
 3.1  Introduction, 53
 3.2  Complexity Analysis, 56
 3.3  Developing Polynomial-Time Algorithms,  66
 3.4  Search Algorithms,  73
 3.5  Flow Decomposition Algorithms,  79
 3.6  Summary,  84
 Reference Notes,  85
 Exercises,  86
 4  SHORTEST PATIO: LABEL-SETTING ALG-ORITHMS, 93
 4.1  Introduction,  93
 4.2  Applications, 97
 4.3  Tree of Shortest Paths,  106
 4.4  Shortest Path Problems in Acyclic Networks,  107
 4.5  Dijkstra's Algorithm,  108
 4.6  Dial's Implementation,  113
 4.7  Heap Implementations,  115
 4.8  Radix Heap Implementation,  116
 4.9  Summary,  121
 Reference Notes,  122
 Exercises,  124
 5 SHORTEST PATHS:LABEL-CORRECTING ALGORITHM,133
 5.1  Introduction,  133
 5.2  Optimality Conditions, 135
 5.3  Generic Label-Correcting Algorithms,  136
 5.4  Special Implementations of the Modified Label-Correcting Algorithm, 141
 5.5  Detecting Negative Cycles,  143
 5.6  All-Pairs Shortest Path Problem,  144
 5.7  Minimum Cost-to-Time Ratio Cycle Problem,  150
 5.8  Summary,  154
 Reference Notes,  156
 Exercises,  157
 6  MAXIMUM FLOWS:BASICC IDEAS, 168
 6.1  Introduction,  166
 6.2  Applications,  169
 6.3  Flows and Cuts,  177
 6.4  Generic Augmenting Path Algorithm,  180
 6.5  Labeling Algorithm and the Max-Flow Min-Cut Theorem,  184
 6.6  Combinatorial Implications of the Max-Flow Min-Cut Theorem,  188
 6.7  Flows with Lower Bounds,  191
 6.8  Summary, 196
 Reference Notes,  197
 Exercises,  198
 7 MAXIMUM FLOWS:POLYNOMIAL ALG-ORITHMS,2O7
 7.1  Introduction, 207
 7.2  Distance Labels, 209
 7.3  Capacity Scaling Algorithm, 210
 7.4  Shortest Augmenting Path Algorithm, 213
 7.5  Distance Labels and Layered Networks, 221
 7.6  Generic Prefiow-Push Algorithm, 223
 7.7  FIFO Prefiow-Push Algorithm, 231
 7.8  Highest-Label Prefiow-Push Algorithm, 233
 7.9  Excess Scaling Algorithm, 237
 7.10  Summary, 241
 Reference Notes, 241
 Exercises, 243
 8  MAXIMUM FLOWS:ADDITIONAL TOPICS,25O
 8.1  Introduction, 250
 8.2  Flows in Unit Capacity Networks, 252
 8.3  Flows in Bipartite Networks, 255
 8.4  Flows in Planar Undirected Networks, 260
 8.5  Dynamic Tree Implementations,  265
 8.6  Network Connectivity, 273
 8.7  All-Pairs Minimum Value Cut Problem, 277
 8.8  Summary, 285
 Reference Notes,  287
 Exercises,  288
 9 MINLMUM COST FLOWS:BASIC ALGORITHMS,294
 9.1  Introduction, 294
 9.2  Applications, 298
 9.3  Optimality Conditions, 306
 9.4  Minimum Cost Flow Duality, 310
 9.5  Relating Optimal Flows to Optimal Node Potentials, 315
 9.6  Cycle-Canceling Algorithm and the Integrality Property, 317
 9.7  Successive Shortest Path Algorithm,  320
 9.8  Primal-Dual Algorithm, 324
 9.9  Out-of-Kilter Algorithm, 326
 9.10  Relaxation Algorithm, 332
 9.11  Sensitivity Analysis, 337
 9.12  Summary, 339
 Reference Notes,  341
 Exercises, 344
 10  MINIMUM COST FLOWS:POLYNOMIAL ALGORITHMS,357
 10.1  Introduction, 357
 10.2  Capacity Scaling Algorithm, 360
 10.3  Cost Scaling Algorithm, 362
 10.4  Double Scaling Algorithm, 373
 10.5  Minimum Mean Cycle-Canceling Algorithm, 376
 10.6  Repeated Capacity Scaling Algorithm, 382
 10.7  Enhanced Capacity Scaling Algorithm,  387
 10.8  Summary, 395
 Reference Notes,  396
 Exercises, 397
 11  MINIMUM COST FLOWS: NETWORK SIMPLEX ALGORITHMS, 402
 11.1  Introduction,  402
 11.2  Cycle Free and Spanning Tree Solutions,  405
 11.3  Maintaining a Spanning Tree Structure,  409
 11.4  Computing Node Potentials and Flows, 411
 11.5  Network Simplex Algorithm, 415
 11.6  Strongly Feasible Spanning Trees,  421
 11.7  Network Simplex Algorithm for the Shortest Path Problem,  425
 11.8  Network Simplex Algorithm for the Maximum Flow Problem,  430
 11.9  Related Network Simplex Algorithms,  433
 11.10  Sensitivity Analysis, 439
 11.11  Relationship to Simplex Method, 441
 11.12  Unimodularity Property, 447
 11.13  Summary, 450
 Reference Notes, 451
 Exercises, 453
 12 ASSIGNMENTS AND MATCHINGS, 461
 12.1  Introduction, 461
 12.2  Applications, 463
 12.3  Bipartite Cardinality Matching Problem, 469
 12.4  Bipartite Weighted Matching Problem, 470
 12.5  Stable Marriage Problem, 473
 12.6  Nonbipartite Cardinality Matching Problem, 475
 12.7  Matchings and Paths, 494
 12.8  Summary, 498
 Reference Notes, 499
 Exercises,  501
 13 MINIMUM SPANNING TREES, 510
 13.1  Introduction, 510
 13.2  Applications, 512
 13.3  Optimality Conditions, 516
 13.4  Kruskai's Algorithm, 520
 13.5  Prim's Algorithm, 523
 13.6  Sollin's Algorithm, 526
 13.7  Minimum Spanning Trees and Matroids,  528
 13.8  Minimum Spanning Trees and Linear Programming,  530
 13.9  Summary, 533
 Reference Notes,  535
 Exercises,  536
 14 CONVEX COST FLOWS, 543
 14.1  Introduction, 543
 14.2  Applications, 546
 14.3  Transformation to a Minimum Cost Flow Problem,  551
 14.4  Pseudopolynomial-Time Algorithms, 554
 14.5  Polynomial-Time Algorithm, 556
 14.6  Summary, 560
 Reference Notes,  561
 Exercises,  562
 15  GENERALIXED FLOWS, 568
 15.1  Introduction, 566
 15.2  Applications, 568
 15.3  Augmented Forest Structures, 572
 15.4  Determining Potentials and Flows for an Augmented Forest Structure,  577
 15.5  Good Augmented Forests and Linear Programming Bases, 582
 15.6  Generalized Network Simplex Algorithm, 583
 15.7  Summary, 591
 Reference Notes, 591
 Exercises,  593
 16  LAGRANGIAN RELAXATION AND NETWORK OPTLMIZATION, 598
 16.1  Introduction, 598
 16.2  Problem Relaxations and Branch and Bound, 602
 16.3  Lagrangian Relaxation Technique,  605
 16.4  Lagrangian Relaxation and Linear Programming, 615
 16.5  Applications of Lagrangian Relaxation, 620
 16.6  Summary, 635
 Reference Notes,  637
 Exercises,  638
 17  MULTICOMMODITY FLOWS, 649
 17.1  Introduction, 649
 17.2  Applications, 653
 17.3  Optimality Conditions, 657
 17.4  Lagrangian Relaxation, 660
 17.5  Column Generation Approach,  665
 17.6  Dantzig-Woffe Decomposition, 671
 17.7  Resource-Directive Decomposition,  674
 17.8  Basis Partitioning, 678
 17.9  Summary, 682
 Reference Notes,  684
 Exercises,  686
 18 COMPUTATIONAL TESTING OF ALGORITHMS, 695
 18.1  Introduction, 695
 18.2  Representative Operation Counts,  698
 18.3  Application to Network Simplex Algorithm,  702
 18.4  Summary,  713
 Reference Notes,  713
 Exercises,  715
 19  ADDITIONAL APPLICATIONS, 717
 19.1  Introduction,  717
 19.2  Maximum Weight Closure of a Graph,  719
 19.3  Data Scaling, 725
 19.4  Science Applications,  728
 19.5  Project Management,  732
 19.6  Dynamic Flows,  737
 19.7  Arc Routing Problems, 740
 19.8  Facility Layout and Location, 744
 19.9  Production and Inventory Planning,  748
 19.10  Summary,  755
 Reference Notes,  759
 Exercises,  760
 APPENDIX A DATA STRUCTURES,  765
 A.1  Introduction,  765
 A.2  Elementary Data Structures,  766
 A.3  d-Heaps,  773
 A.4  Fibonacci Heaps,  779
 Reference Notes, 787
 APPENDIX B N9-COMPLETENESS, 788
 B.1  Introduction,  788
 B.2  Problem Reductions and Transformations,  790
 B.3  Problem Classes 9,N9, N9-Complete, and N9-Hard,  792
 B.4  Proving N9-Completeness Results,  796
 B.5  Concluding Remarks, 800
 Reference Notes, 801
 APPENDIX C  LINEAR PROGRAMMING,  802
 C.1  Introduction, 802
 C.2  Graphical Solution Procedure,  804
 C.3  Basic Feasible Solutions,  805
 C.4  Simplex Method, 810
 C.5  Bounded Variable Simplex Method, 814
 C.6  Linear Programming Duality, 816
 Reference Notes,  820
 REFERENCES, 821
 INDEX, 84O
</font>
猜您喜欢

读书导航