Answers are grounded in this paper and cite their sources.
Let M = (N, ℱ) be a matroid. Suppose that each element i in N is associated with an ordered pair of rational numbers (a i , b i ). For each subset S in ℱ define A(S) = ∑ i∈S a i and B(S) = ∑ i∈S b i . Let g be a real convex function defined on R 2 . Consider the problem of maximizing g(A(S), B(S)) over all bases S of M. We 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 we apply appropriate transformations to obtain strongly polynomial algorithms for some cases when g is not polynomial. In particular, we find in strongly polynomial time the minimal cost reliability ratio spanning tree of an undirected graph.
No takes yet. Share an insight, caveat, or question.
Hassin et al. (1989) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: