  We consider a linear relaxation of a generalized minimum-cost network flow
problem with binary input dependencies. In this model the flows through certain
arcs are bounded by linear (or more generally, piecewise linear concave)
functions of the flows through other arcs. This formulation can be used to
model interrelated systems in which the components of one system require the
delivery of material from another system in order to function (for example,
components of a subway system may require delivery of electrical power from a
separate system). We propose and study randomized rounding schemes for how this
model can be used to approximate solutions to a related mixed integer linear
program for modeling binary input dependencies. The introduction of side
constraints prevents this problem from being solved using the well-known
network simplex algorithm, however by characterizing its basis structure we
develop a generalization of network simplex algorithm that can be used for its
efficient solution.
