Weight reduction problems with certain bottleneck objectives
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 and a cost . For each e?E, c(e) stands for the cost of reducing weight w(e) by one unit. For each subset , 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 -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 . In particular we outline a polynomial algorithm in the case when is the class of all spanning trees in an undirected graph.
weight reduction capacity expansion transversal set bottleneck problem computational complexity