This paper is concerned with bottleneck weight reduction problems (WRPs) stated as follows. We are given a finite set E, a class ℱ of nonempty subsets of E, a weight w:E → ℜ+ and a cost c:E → ℜ+. For each e∈E, c(e) stands for the cost of reducing weight w(e) by one unit. For each subset F ∈ ℱ, the bottleneck weight of F is w(F)=mine∈Fw(e). The weight of the family ℱ is the maximum of w(F) for all F in ℱ. The problem is to determine new weights x(e)⩽w(e) such that the weight of ℱ is minimized under the constraint that the overall reduction cost does not exceed a given budget B. Similarly to capacity expansion problems, WRPs include NP-hard problems. A WRP can be formulated as a parametric optimization problem over all transversal sets T of the class ℱ. This leads to (strongly) polynomial solution procedures for special systems F. In particular we outline a polynomial algorithm in the case when ℱ is the class of all spanning trees in an undirected graph.
