A capacity expansion problem with budget constraint and bottleneck limitation

This paper considers a capacity expansion problem with a budget constraint. Suppose each edge in the network has two attributes: capacity and the degree of difficulty. The difficulty degree of a tree T is the maximum degree of difficulty of all edges in the tree and the cost for coping with the difficulty in a tree is a nondecreasing function of the difficulty degree of the tree. The paper considers a case where one needs to increase the capacities of some edges so that there is a spanning tree whose capacity can be increased to the maximum extent, while the total cost for increasing capacity as well as overcoming the difficulty in the spanning tree does not exceed a given budget D*. Suppose the cost for increasing capacity on each edge is a linear function of the increment of capacity. The authors transform this problem into that of solving some hybrid parametric spanning tree problems and propose a strongly polynomial algorithm.