Increasing the Capacity of a Network: The Parametric Budget Problem

The problem considered in this paper is that of allocating a budget of resources among the links of a network for the purpose of increasing its flow capacity relative to given sources and sinks. On the assumption that the cost of increasing each link capacity is linear, a labeling algorithm is described that permits rapid calculation of optimal allocations for all budgets.

• 저널Management Science · 5(4) · 472–483
• 토픽Optimization and Mathematical Programming · Control and Systems Engineering
• DOI10.1287/mnsc.5.4.472
• 저자D. R. Fulkerson