Combinatorial optimization 组合优化

Perceptively written text examines optimization problems that can be formulated in terms of networks and algebraic structures called matroids. Chapters cover shortest paths, network flows, bipartite matching, nonbipartite matching, matroids and the greedy algorithm, matroid intersections, and the matroid parity problems. A suitable text or reference for courses in combinatorial computing and concrete computational complexity in departments of computer science and mathematics.

Preface
Chapter 1 INTRODUCTION
1. What is Combinatorial Optimization ?
2. Some Representative Optimization Problems
3. When is a Problem Solved?
4. The Criterion of Polynomial Boundedness
5. Some Apparently Nonpolynomial-Bounded Problem:
6. Methods of Solution
Comments and References
Chapter 2 MATHEMATICAL PRELIMINARIES
1. Mathematical Prerequisites
2. Sets and Relations
3. Graphs and Digraphs
4. Subgraphs, Cliques, Multigraphs
5. Connectivity in Graphs
6. Connectivity in Digraphs
7. Cocyeles and Directed Coeycles
8. Planarity and Duality
9. Eulerian and Hami'ltonian Graphs
10. Linear Programming Problems
II. The Simplex Method
12. Geometric Interpretation
13. Duality Theory
Comments and References
Chapter 3 SHORTEST PATHS
1. Introduction
2. Some Problem Formulations
3. Bellman's Equations
4. Acyclic Networks
5. Networks with Positive Arcs: Dijkstra's Method
6. Solution by Successive Approximations." Bellman-Ford Method
Method
7. Improvements in Efficiency: Yen's Modifications
8. Linear Programming Interpretation and Relaxation
Procedures
9. Shortest Paths between all Pairs of Nodes: Matrix
Multiplication
10. Floyd-Warshall Method
11. Detection of Negative Cycles
12. Networks with Transit Times
13. The Minimal Cost-to-time Ratio Cycle Problem
14. M Shortest Paths: Dreyfus Method
15. M Shortest Paths without Repeated Nodes
Comments and References
Chapter 4 NETWORK FLOWS
1. Introduction
2. Maximal Flows
3. Maximal Flow Algorithm
4. Efficiency of the Maximal Flow Algorithm
5. Combinatorial Implications of Max-Flow Min-Cut Theorem
6. Linear Programming Interpretation of Max-Flow Min-Cut Theorem
7. Minimum Cost Flows
8. Networks with Losses and Gains
9. Lower Bounds and Circulations
10. The Out-of-Kilter Method
11. Theoretical Improvement in Efficiency of Out-oJ:Kilter Method
12. Integrality of Flows and the Unimodular Property
13. Application to Project Scheduling
14. Transhipment and Transportation Problems
Chapter 5 BIPARTTE MATCHING
Chapter 6 NONBIPARTITE MATCHING
Chapter 7 MATROIDS AND THE GREEDY ALGORITHM
Chapter 8 MATROID INTERSCETIONGS
Chapter 9 THE MATROID PARITY PROBLEM
Auther Index
Subject Index