Combinatorial Optimization:Algorithms and Complexity

Combinatorial Optimization
分享
扫描下方二维码分享到微信
打开微信,点击右上角”+“,
使用”扫一扫“即可将网页分享到朋友圈。
作者:
出版社: Oversea Publishing House
1998-01
版次: 1
ISBN: 9780486402581
定价: 187.50
装帧: 平装
开本: 其他
纸张: 胶版纸
页数: 528页
正文语种: 英语
  • Clearlywrittengraduate-leveltextconsiderstheSovietellipsoidalgorithmforlinearprogramming;efficientalgorithmsfornetworkflow,matching,spanningtrees,andmatroids;thetheoryofNP-completeproblems;approximationalgorithms,localsearchheuristicsforNP-completeproblems,more."Mathematicianswishingaself-containedintroductionneedlooknofurther." PREFACE TO THE DOVER EDITION PREFACE

    Chapter 1 OPTIMIZATION PROBLEMS

     1.1 Introduction

     1.2 Optimization Problems

     1.3 Neighborhoods

     1.4 Local and Global Optima

     1.5 Convex Sets and Functions

     1.6 Convex Programming Problems

     Problems

     Notes and References

     Appendix: Terminology and Notation

     A.1 Linear Algebra

     A.2 Graph Theory

     A.3 Pidgin Algol

    Chapter2 THE SIMPLEX ALGORITHM

     2.1  Forfns of the Linear Programming Problem

     2.2 Basic Feasible Solutions

     2.3 The Geometry of Linear Programs

      2.3.1  Linear and Affine Spaces

      2.3.2 Convex Polytopes

      2.3.3 Polytopes and LP

     2.4 Moving from bfs to bfs

     2.5 Organization of a Tableau

     2.6 Choosing a Profitable Column

     2.7 Degeneracy and Bland's Anticycling Algorithm

     2.8 Beginning the Simplex Algorithm

     2.9 Geometric Aspects of Pivoting

     Problems

     Notes and References

    Chapter 3 DUALITY

     3.1 The Dual of a Linear Program in General Form

     3.2 Complementary Slackness

     3.3 Farkas' Lemma

     3.4 The Shortest-Path Problem and Its Dual

     3.5 Dual Information in the Tableau

     3.6 The Dual Simplex Algorithm

     3.7 Interpretation of the Dual Simplex Algorithm

     Problems

     Notes and References

    Chapter 4 COMPUTATIONAL CONSIDERATIONS FOR THE SIMPLEX ALGORITHM

     4.1 The Revised Simplex Algorithm

     4.2 Computational Implications of the Revised Simple Algorithm

     4.3 The Max-Flow Problem and Its Solution by the Revised Method

     4.4 Dantzig-Wolfe Decomposition

     Problems

     Notes and References

    Chapter 5 THE PRIMAL-DUAL ALGORITHM

    Chapter 6 PRIMAL-DUAL ALGORITHMS FOR MAX-FLOW AND SHORTEST PATH:FORD-FULKERSON AND DIJKSTRA

    Chapter 7 PRIMAL-DUAL ALGORITHMS FOR MIN-COST FLOW

    Chapter 8 ALGORIT MS AND COMPLEXITY

    Chapter 9 EFFICIENT ALGORITHMS FOR THE  MAX-FLOW PROMBLEM

    Chapter 10 ALGORITHMS FOR MATCHING

    Chapter 11 WEIGHTED MATCHING

    Chapter 12 SPANNING TREES AND MATROIDS

    Chapter 13 INTEGER LINEAR PROGRAMMING

    Chapter 14 A CUTTING-PLANE ALGORITHM FOR INTEGER LINEAR PROGRAMS

    Chapter 15 NP-COM PLETE PROBLEMS

    Chapter 16 MORE ABOUT NP-COMPLETENESS

    Chapter 17 APPROXIMATION ALGORITHMS

    Chapter 18 BRANCH-AND-BOUND AND DYNAMIC PROGRAMMING

    Chapter 19 LOCAL SEARCH

    INDEX
  • 内容简介:
    Clearlywrittengraduate-leveltextconsiderstheSovietellipsoidalgorithmforlinearprogramming;efficientalgorithmsfornetworkflow,matching,spanningtrees,andmatroids;thetheoryofNP-completeproblems;approximationalgorithms,localsearchheuristicsforNP-completeproblems,more."Mathematicianswishingaself-containedintroductionneedlooknofurther."
  • 目录:
    PREFACE TO THE DOVER EDITION PREFACE

    Chapter 1 OPTIMIZATION PROBLEMS

     1.1 Introduction

     1.2 Optimization Problems

     1.3 Neighborhoods

     1.4 Local and Global Optima

     1.5 Convex Sets and Functions

     1.6 Convex Programming Problems

     Problems

     Notes and References

     Appendix: Terminology and Notation

     A.1 Linear Algebra

     A.2 Graph Theory

     A.3 Pidgin Algol

    Chapter2 THE SIMPLEX ALGORITHM

     2.1  Forfns of the Linear Programming Problem

     2.2 Basic Feasible Solutions

     2.3 The Geometry of Linear Programs

      2.3.1  Linear and Affine Spaces

      2.3.2 Convex Polytopes

      2.3.3 Polytopes and LP

     2.4 Moving from bfs to bfs

     2.5 Organization of a Tableau

     2.6 Choosing a Profitable Column

     2.7 Degeneracy and Bland's Anticycling Algorithm

     2.8 Beginning the Simplex Algorithm

     2.9 Geometric Aspects of Pivoting

     Problems

     Notes and References

    Chapter 3 DUALITY

     3.1 The Dual of a Linear Program in General Form

     3.2 Complementary Slackness

     3.3 Farkas' Lemma

     3.4 The Shortest-Path Problem and Its Dual

     3.5 Dual Information in the Tableau

     3.6 The Dual Simplex Algorithm

     3.7 Interpretation of the Dual Simplex Algorithm

     Problems

     Notes and References

    Chapter 4 COMPUTATIONAL CONSIDERATIONS FOR THE SIMPLEX ALGORITHM

     4.1 The Revised Simplex Algorithm

     4.2 Computational Implications of the Revised Simple Algorithm

     4.3 The Max-Flow Problem and Its Solution by the Revised Method

     4.4 Dantzig-Wolfe Decomposition

     Problems

     Notes and References

    Chapter 5 THE PRIMAL-DUAL ALGORITHM

    Chapter 6 PRIMAL-DUAL ALGORITHMS FOR MAX-FLOW AND SHORTEST PATH:FORD-FULKERSON AND DIJKSTRA

    Chapter 7 PRIMAL-DUAL ALGORITHMS FOR MIN-COST FLOW

    Chapter 8 ALGORIT MS AND COMPLEXITY

    Chapter 9 EFFICIENT ALGORITHMS FOR THE  MAX-FLOW PROMBLEM

    Chapter 10 ALGORITHMS FOR MATCHING

    Chapter 11 WEIGHTED MATCHING

    Chapter 12 SPANNING TREES AND MATROIDS

    Chapter 13 INTEGER LINEAR PROGRAMMING

    Chapter 14 A CUTTING-PLANE ALGORITHM FOR INTEGER LINEAR PROGRAMS

    Chapter 15 NP-COM PLETE PROBLEMS

    Chapter 16 MORE ABOUT NP-COMPLETENESS

    Chapter 17 APPROXIMATION ALGORITHMS

    Chapter 18 BRANCH-AND-BOUND AND DYNAMIC PROGRAMMING

    Chapter 19 LOCAL SEARCH

    INDEX
查看详情
好书推荐 / 更多
Combinatorial Optimization
唐宋时期的雕版印刷
宿白
Combinatorial Optimization
文本及其不满
黄子平
Combinatorial Optimization
显微镜下的成都
王笛 著
Combinatorial Optimization
矮人星上的矮人(翁贝托·埃科作品系列)
翁贝托·埃科 、欧金尼奥·卡尔米 著;王建全 译
Combinatorial Optimization
人生档案:波兰当代戏剧家剧作选
黄珊、赵祯 译;维托尔德·贡布罗维奇;塔代乌什·鲁热维奇;斯拉沃米尔·姆罗热克;斯塔尼斯瓦夫·伊格纳奇·维特凯维奇
Combinatorial Optimization
一个利他主义者之死
奥伦·哈曼 著
Combinatorial Optimization
谁都可以画漫画!手冢治虫大师班
甘卉 、后浪 译;[日]手冢治虫
Combinatorial Optimization
杜甫:中国最伟大的诗人(史学大家洪业唯一专书著述,哈佛大学出版社研究作品,BBC热播同名杜甫纪录片重点参考,梁文道“开卷八分钟”特别推荐)
洪业 著;曾祥波 译
Combinatorial Optimization
数学之美 第三版
吴军
Combinatorial Optimization
俄苏文学经典译著·盗用公款的人们
卡泰耶夫 著;小莹 译
Combinatorial Optimization
十三行小字中央
江弱水 著
Combinatorial Optimization
两京十五日(全2册)马伯庸全新作品
马伯庸 著