An oracle strongly polynomial algorithm for bottleneck expansion problems

摘要

Let E = {e_1, e_2, …, e_n} be a finite set and F be a family of subsets of E. For each element e_i in E, c_i is a given capacity and w_i is the cost of increasing capacity c_i by one unit. The problem is how to expand the capacities of elements in E so that the capacity of F is as large as possible, subject to a given budget restriction. This problem was introduced in [1] where an algorithm was proposed which is polynomial under some conditions. However, that method is not strongly polynomial. In this paper this problem is solved by solving a combinatorial equation. It is shown that if the problem min_(F∈F)w(F) is solvable in strongly polynomial time, then the bottleneck expansion problem is also solvable in strongly polynomial time. This result is stronger than what the method in [1] gives. In addition, some interesting variations of this problem are also discussed.