On the optimum capacity of capacity expansion problems (Q2472185)

The authors consider several capacity expansion problems. Given a finite set \(E=\{e_1, \ldots, e_n\}\) with a capacity \(c_i\) for each \(e_i\) and a family \({\mathcal F}\) of subsets \(F\) of \(E\), the goal is to find an optimal capacity value \(r^*\) such that the efficiency \(f(r^*)\) minus the cost \(\Phi(r^*)\) of the expansion is maximized. They consider several cases. They show for the case of bottleneck expansion with sum cost function the problem can be solved efficiently if an efficient algorithm for the maximum weighted capacity problem is available. For the case of sum expansion with sum cost and bottleneck expansion and bottleneck cost, similar results are shown. Finally the authors investigate the capacity expansion problem for maximum flow and show that it can bes solved in polynomial time.