Let , be two weight functions on the possible edges of a directed or undirected graph with vertex set V such that for the cut function, the inequality holds for every . The paper considers the computation of the value defined by . It shows that the associated decision problem is NP-complete, but for a class of instances the paper can give a polynomial time algorithm. This class is closely related to the following bottleneck augmentation problem. Consider a network, with a rational valued capacity funtion , and let k be a positive, rational number. Consider the problem of finding a capacity function such that, in the resulting network the edge connectivity number is at least k, and the maximal increase is minimal. The paper gives an algorithm which computes such an augmentation in strongly polynomial time.
