Combinatorial optimization : theory and algorithms

>> Google Books

所蔵情報QRコード

Combinatorial optimization : theory and algorithms / Bernhard Korte, Jens Vygen

資料種別:

図書

出版情報:

Berlin ; Tokyo : Springer-Verlag, c2000

形態:

xi, 530 p. ; 25 cm

シリーズ名:

Algorithms and combinatorics ; 21 <BA00544068>

著者名:

ISBN:

9783540672265 [3540672265]

書誌ID:

BA47200572

子書誌情報

フルテキスト

所蔵情報

他の版・巻

Combinatorial optimization : theory and algorithms. 5th ed (: pbk)
Bernhard Korte, Jens Vygen , Springer-Verlag , c2012

書誌詳細

注記:

Includes bibliographical references and indexes

主題:

確率論．数理統計学

言語:

英語

目次情報:

Introduction / 1：

Enumeration / 1.1：

Running Time of Algorithms / 1.2：

Linear Optimization Problems / 1.3：

Sorting / 1.4：

Exercises

References

Graphs / 2：

Basic Definitions / 2.1：

Trees, Circuits, and Cuts / 2.2：

Connectivity / 2.3：

Eulerian and Bipartite Graphs / 2.4：

Planarity / 2.5：

Planar Duality / 2.6：

Linear Programming / 3：

Polyhedra / 3.1：

The Simplex Algorithm / 3.2：

Duality / 3.3：

Convex Hulls and Polytopes / 3.4：

Linear Programming Algorithms / 4：

Size of Vertices and Faces / 4.1：

Continued Fractions / 4.2：

Gaussian Elimination / 4.3：

The Ellipsoid Method / 4.4：

Khachiyan's Theorem / 4.5：

Separation and Optimization / 4.6：

Integer Programming / 5：

The Integer Hull of a Polyhedron / 5.1：

Unimodular Transformations / 5.2：

Total Dual Integrality / 5.3：

Totally Unimodular Matrices / 5.4：

Cutting Planes / 5.5：

Lagrangean Relaxation / 5.6：

Spanning Trees and Arborescences / 6：

Minimum Spanning Trees / 6.1：

Minimum Weight Arborescences / 6.2：

Polyhedral Descriptions / 6.3：

Packing Spanning Trees and Arborescences / 6.4：

Shortest Paths / 7：

Shortest Paths From One Source / 7.1：

Shortest Paths Between All Pairs of Vertices / 7.2：

Minimum Mean Cycles / 7.3：

Network Flows / 8：

Max-Flow-Min-Cut Theorem / 8.1：

Menger's Theorem / 8.2：

The Edmonds-Karp Algorithm / 8.3：

Blocking Flows / 8.4：

The Goldberg-Tarjan Algorithm / 8.5：

Gomory-Hu Trees / 8.6：

The Minimum Cut in an Undirected Graph / 8.7：

Minimum Cost Flows / 9：

Problem Formulation / 9.1：

An Optimality Criterion / 9.2：

Minimum Mean Cycle-Cancelling Algorithm / 9.3：

Successive Shortest Path Algorithm / 9.4：

Orlin's Algorithm / 9.5：

Maximum Matchings / 10：

Bipartite Matching / 10.1：

The Tutte Matrix / 10.2：

Tutte's Theorem / 10.3：

Ear-Decompositions of Factor-Critical Graphs / 10.4：

Edmonds' Matching Algorithm / 10.5：

Weighted Matching / 11：

The Assignment Problem / 11.1：

Outline of the Weighted Matching Algorithm / 11.2：

Implementation of the Weighted Matching Algorithm / 11.3：

Postoptimality / 11.4：

The Matching Polytope / 11.5：

b-Matchings and T-Joins / 12：

b-Matchings / 12.1：

Minimum Weight T-Joins / 12.2：

T-Joins and T-Cuts / 12.3：

The Padberg-Rao Theorem / 12.4：

Matroids / 13：

Independence Systems and Matroids / 13.1：

Other Matroid Axioms / 13.2：

The Greedy Algorithm / 13.3：

Matroid Intersection / 13.5：

Matroid Partitioning / 13.6：

Weighted Matroid Intersection / 13.7：

Generalizations of Matroids / 14：

Greedoids / 14.1：

Polymatroids / 14.2：

Minimizing Submodular Functions / 14.3：

NP-Completeness / 15：

Turing Machines / 15.1：

Church's Thesis / 15.2：

P and NP / 15.3：

Cook's Theorem / 15.4：

Some Basic NP-Complete Problems / 15.5：

The Class coNP / 15.6：

NP-Hard Problems / 15.7：

Approximation Algorithms / 16：

Set Covering / 16.1：

Colouring / 16.2：

Approximation Schemes / 16.3：

Maximum Satisfiability / 16.4：

The PCP Theorem / 16.5：

L-Reductions / 16.6：

The Knapsack Problem / 17：

Fractional Knapsack and Weighted Median Problem / 17.1：

A Pseudopolynomial Algorithm / 17.2：

A Fully Polynomial Approximation Scheme / 17.3：

Bin-Packing / 18：

Greedy Heuristics / 18.1：

An Asymptotic Approximation Scheme / 18.2：

The Karmarkar-Karp Algorithm / 18.3：

Multicommodity Flows and Edge-Disjoint Paths / 19：

Multicommodity Flows / 19.1：

Algorithms for Multicommodity Flows / 19.2：

Directed Edge-Disjoint Paths Problem / 19.3：

Undirected Edge-Disjoint Paths Problem / 19.4：

Network Design Problems / 20：

Steiner Trees / 20.1：

Survivable Network Design / 20.2：

A Primal-Dual Approximation Algorithm / 20.3：

Jain's Algorithm / 20.4：

The Traveling Salesman Problem / 21：

Approximation Algorithms for the TSP / 21.1：

Euclidean TSPs / 21.2：

Local Search / 21.3：

The Traveling Salesman Polytope / 21.4：

Lower Bounds / 21.5：

Branch-and-Bound / 21.6：

Notation Index

Author Index

Subject Index

Introduction / 1：

Enumeration / 1.1：

Running Time of Algorithms / 1.2：

Linear Optimization Problems / 1.3：

Sorting / 1.4：

Exercises

続きを見る

ブックレビュー

類似資料:

1 図書 Combinatorial optimization : theory and algorithms Korte, Bernhard H., 1938-, Vygen, Jens Springer	7 電子ブック Integer Programming and Combinatorial Optimization Jon Lee, Jens Vygen, Kittler, Josef, Vygen, Jens SpringerLink Books - AutoHoldings, Springer International Publishing
2 図書 Combinatorial optimization : theory and algorithms (: pbk) Korte, Bernhard H., 1938-, Vygen, Jens Springer-Verlag	8 電子ブック Integer Programming and Combinatorial Optimization : 25th International Conference, IPCO 2024, Wroclaw, Poland, July 3-5, 2024, Proceedings Vygen, Jens., Byrka, Jarosław SpringerLink Books - AutoHoldings, Springer International Publishing AG
3 電子ブック Combinatorial Optimization Korte, Bernhard, Vygen, Jens SpringerLink Books - AutoHoldings, Springer Berlin Heidelberg	9 図書 Paths, flows, and VLSI-layout (: gw) Korte, Bernhard H., 1938- Springer-Verlag
4 電子ブック Ottimizzazione Combinatoria Korte, Bernhard, Vygen, Jens SpringerLink Books - AutoHoldings, Springer Milan	10 図書組合せ最適化 : 理論とアルゴリズム Korte, Bernhard H., 1938-, Vygen, Jens, 浅野, 孝夫(1949-), 平田, 富夫(1949-), 小野, 孝男, 浅野, 泰仁シュプリンガー・フェアラーク東京
5 図書 Modern applied mathematics : optimization and operations research : collection of state-of-the-art surveys based on lectures presented at the summer school … (: Elsevier ; : North-Holland) Korte, Bernhard H., 1938- North-Holland, Sole distributors for the U.S.A. and Canada, Elsevier Science Pub. Co.	11 図書組合せ最適化 : 理論とアルゴリズム Korte, Bernhard H., 1938-, Vygen, Jens, 浅野, 孝夫(1949-), 浅野, 泰仁, 平田, 富夫(1949-) 丸善出版
6 電子ブック Integer Programming and Combinatorial Optimization Jon Lee, Jens Vygen Springer eBooks Computer Science, Springer International Publishing	12 図書組合せ最適化 : 理論とアルゴリズム Korte, Bernhard H., 1938-, Vygen, Jens, 浅野, 孝夫(1949-), 平田, 富夫(1949-), 小野, 孝男, 浅野, 泰仁シュプリンガー・ジャパン