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
理想国译丛043:资本主义的未来
[英]保罗·科利尔 著
Combinatorial Optimization
1789:三城记
[英]迈克·拉波特 著;夏天 译
Combinatorial Optimization
当所有愿望实现:以自由,以死亡
[奥]托马斯·格拉维尼奇 著;刘海宁 译
Combinatorial Optimization
寻找昨日书店
艾米·迈耶森 著;王马奇 译
Combinatorial Optimization
咫尺天涯:最后的老北京
肖复兴
Combinatorial Optimization
醉钢琴与地下蓝调:汤姆·威兹谈汤姆·威兹
[美]小保罗·马赫 编;业之 译
Combinatorial Optimization
上海早期影迷文化史(1897-1937)
侯凯 著
Combinatorial Optimization
动画表演规律:让你的角色活起来(全球畅销经典版)
[加]南希·贝曼(Nancy Beiman) 著;王瑶 译
Combinatorial Optimization
巴黎评论·作家访谈5(“巴黎评论·作家访谈系列”新一辑,共收录以下十六位作家的长篇访谈)
美国《巴黎评论》编辑部
Combinatorial Optimization
满是空虚之物
[日]阿伏伽德六 著;黄文娟 译
Combinatorial Optimization
金冲及文丛·一本书的历史:胡乔木、胡绳谈《中国共产党的七十年》
金冲及 著
Combinatorial Optimization
仿佛若有光:大理访谈录如果你渴望改变,去大理吧!那里有来自全世界的文化异质者,那里有一切可能!
黄菊 著