Let D=(V,A) be a directed graph. A real-valued vector x defined on the arc set A is a max-balanced flow for D if for every cut W the maximum weight over arcs leaving W equals the maximum weight over arcs entering W. For vectors l•u defined on A, the authors describe an analogue of Hoffman’s circulation conditions for the existence of a max-balanced flow x satisfying l•x•u. They describe an algorithm for computing such a vector, but show that minimizing a linear function over the set of max-balanced flows satisfying l•x•u is NP-hard. The authors show that the set of all max-balanced flows satisfying l•x•u has a greatest element under the usual coordinate partial order, and they describe an algorithm for computing this element. This allows the authors to solve several related approximation problems. They also investigate the set of minimal elements under the coordinate partial order. The authors describe an algorithm for finding a minimal element and show that counting the number of minimal elements is ℝP-hard. Many of the present algorithms exploit the relationship between max-balanced flows and bottleneck paths.
