Minimum-cost flows in convex-cost networks |
| |
Authors: | T. C. Hu |
| |
Abstract: | An algorithm is given for solving minimum-cost flow problems where the shipping cost over an arc is a convex function of the number of units shipped along that arc. This provides a unified way of looking at many seemingly unrelated problems in different areas. In particular, it is shown how problems associated with electrical networks, with increasing the capacity of a network under a fixed budget, with Laplace equations, and with the Max-Flow Min-Cut Theorem may all be formulated into minimum-cost flow problems in convex-cost networks. |
| |
Keywords: | |
|
|