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

    [Return to Athena Scientific Homepage]
    info@athenasc.com