# Network Flows and Monotropic Optimization Table of Contents:

1. Networks

1. Definition of a Network
2. Examples of Networks
3. Incidences
4. Flows
5. Divergence
6. Vector Operations
7. Circulations and the Augmented Network
8. Dynamic Version of a Network
9. Potentials and Tension
10. Preview of Optimal Flows and Potentials
11. Some Generalizations
12. Exercises
13. Comments and References

2. Paths and Cuts

1. Paths
2. Incidences for Paths
3. Connectedness
4. Finding a Path from One Place to Another
5. Cuts
6. Painted Network Algorithm
7. Priority Rules and Multiroutings
8. Theoretical Implications of the Algorithm
9. Application to Connectedness
10. Acyclic Networks
11. Planar Networks and Duality
12. Exercises
13. Comments and References

3. Flows and Capacities

1. Capacity Intervals
2. Flux across a Cut
3. Max Flow Problem
4. Max Flow Min Cut
5. Nature of the Min Cut Problem
6. Max Flow Algorithm
7. Commensurability and Termination
8. Feasible Flows
9. Feasible Distribution Algorithm
10. Multipath Implementation
11. Flow Rectification Algorithm
12. Node Capacities and Dynamic Flows
13. Exercises
14. Comments and References

4. Analysis of Flow

1. Integral Flows
2. Conformal Realization of Flows
3. Realization Algorithm
4. Justification of the Algorithm
5. Trees
6. Forrests and Spanning Trees
7. Tucker Representations of the Circulation Space
8. Basic Theorem
9. Pivoting
10. Extreme Flows
11. Extremal Representation Algorithm
12. Exercises
13. Comments and References

5. Matching Theory and Assignment Problems

6. Matching Problem
7. Matching Algorithm
8. Assignments
9. Application to Partially Ordered Sets
10. Optimal Assignments
11. Hungarian Assignment Algorithm
12. Matching with Multiplicities
13. Bottleneck Optimization
14. Exercises
15. Comments and References

• Potentials and Spans

1. Spread Relative to a Path
2. Optimal Paths
3. Max Tension Min Path
4. Min Path Algorithm
5. Node-Scanning Implementation
6. Feasible Potentials
7. Feasible Differential Theorem
8. Refinements
9. Tension Rectification Algorithm
10. Optimal Routings
11. Routing Optimization Procedure
12. Integral and Extreme Differentials
13. Exercises
14. Comments and References

• Networks with Linear Costs

1. Linear Optimal Distribution Problem
2. Examples of Optimization of Flows
3. Optimal Distribution Algorithm
4. Simplex Method for Flows
5. Linear Optimal Differential Problem
6. Examples of Optimization of Potentials
7. Optimal Differential Algorithm
8. Simplex Algorithm for Potentials
9. Duality and the Elementary Problems
10. Thrifty Adjustment Algorithm
11. Interpretations
12. Multipath Implementation
13. Out-of-Kilter Algorithm
14. Exercises
15. Comments and References

• Optimal Flows and Potentials

1. Convex Cost Functions
2. Characteristic Curves
3. Piecewise Linear or Quadratic Costs
4. Optimal Distribution Problem
5. Conjugate Costs
6. Examples of Conjugate Functions
7. Optimal Differential Problem
8. Duality Theorem and Equilibrium Conditions
9. Equilibrium Models
10. Improvement of Flows
11. Improvement of Potentials
12. Existence of Solutions
13. Boundeness of Optimizing Sequences
14. Black Boxes
15. Exercises
16. Comments and References

• Algorithms for Convex Costs

1. Optimal Distribution Algorithm
2. Application to Piecewise Linear Problems
3. Optimal Differential Algorithm
4. Thrifty Adjustment Algorithm (Piecewise Linear)
5. Application to Black Boxes
6. Out-of-Kilter Algorithm (Piecewise Linear)
7. Termination and Refinements
8. Fortified Algorithms and the Duality Theorem
9. Discretized Descent Algorithms
10. Calculating epsilon-Optimal Solutions
11. Optimizing Sequences and Piecewise Linearization
12. Convex Simplex Method
13. Exercises
14. Comments and References

• Linear Systems of Variables

1. Primal and Dual Variables
2. Elementary Vectors and Supports
3. Bases
4. Networks with Gains
5. A Generalization of Circuits and Cuts
6. Multicommodity Systems and Factorization
7. Painted Index Theorem and Algorithm
8. Termination and Preprocessing
9. Constraints and Feasibility
10. Rectification Algorithms
11. Shortcuts in Pivoting Implementation
12. Augmented and Aggregated Formats
13. Extreme Solutions
14. Exercises
15. Comments and References

• Monotropic Programming

1. Optimization and Equilibrium
2. Examples of Monotropic Programming
3. Descent by Elementary Vectors
4. Duality and the Existence of Solutions
5. Boundedness Property
6. Decomposition
7. Application to Traffic Equilibrium
8. Basic Descent Algorithms
9. Fortified and Discretized Descent
10. Simplex Methods
11. General Out-of-Kilter Algorithm
12. Other Formats and Termination
13. Parametric Programming
14. Exercises
15. Comments and References

• Bibliograpgy

• Index