Minimum-cost circulation In this problem, we consider a variant of the minimum-cost-flow problem from Section 29.2 in which we are not given a demand, a source, or a sink. Instead, we are given, as before, a flow network and edge costs a(u, v)a(u, v) flow is feasible if it satisfies the capacity constraint on every edge and flow conservation at every vertex. The goal is to find, among all feasible flows, the one of minimum cost. We call this problem the minimum-cost-circulation problem.
A. Formulate the minimum-cost-circulation problem as a linear program.
B. Suppose that for all edges (u, v) E E, we have a (u, v)> 0. Characterize an optimal solution to the minimum cost-circulation problem.
C. Formulate the maximum-flow problem as a minimum cost-circulation problem linear program. That is given a maximum-flow problem instance (V, E) with source s, sink t and edge capacities c, create a minimum-cost circulation (V',E) with edge problem by giving a (possibly different network G capacities c and edge costs a such that you can discern a solution to the maximum-flow problem from a solution to the minimum-cost-circulation prob- lem.
D. Formulate the single-source shortest-path problem as a minimum cost-circu- lation problem linear program.