Let M=(N,ℱ) be a matroid. Suppose that each element i in N is associated with an ordered pair of rational numbers (ai,bi). For each subset S in ℱ define A(S)=ΣiÅ∈Sai and B(S)=ΣiÅ∈Sbi. Let g be a real convex function defined on R2. Consider the problem of maximizing g(A(S), B(S)) overall bases S of M. The authors present a polynomial algorithm for this problem when g is a general polynomial. This algorithm is strongly polynomial when the degree of g is at most cubic. Using the latter result the authors apply appropriate transformations to obtain strongly polynomial algorithms for some cases when g is not polynomial. In particular, they find in strongly polynomial time the minimal cost reliability ratio spanning tree of an undirected graph.
