Lexicographically Optimal Base of a Polymatroid with Respect to a Weight Vector
研究了多拟阵中相对于权重向量的字典序最优基，给出了刻画其与权重向量关系的定理，并提出了求解唯一最优基及进行灵敏度分析的算法，可用于多源多汇网络中的字典序最优流问题。
Let (E, ρ) be a polymatroid with a ground set E and a rank function ρ. A base x = (x(e)) ϵ ∈ E of polymatroid (E, ρ) is called a lexicographically optimal base of (E, ρ) with respect to a weight vector w = (w(e)) ϵ∈E if the |E|-tuple of the numbers x(e)/w(e)(e∈E) arranged in order of increasing magnitude is lexicographically maximum among all |E|-tuples of numbers y(e)/w(e)(e ∈ E) arranged in the same manner for all bases y = (y(e)) e∈E of (E, ρ). We give theorems that characterize the relationship between weight vectors and lexicographically optimal bases and point out that a lexicographically optimal base minimizes among all bases a quadratic objective function defined in terms of the associated weight vector. Also, we present an algorithm for finding the (unique) lexicographically optimal base with respect to a given weight vector. Furthermore, we consider the problem of determining the set of weight vectors with respect to which a given base is lexicographically optimal and provide an algorithm for solving it, which is useful for the sensitivity analysis of the optimal base with regard to the variation of the weight vector. The algorithms proposed in the present paper efficiently solve the problem, treated by N. Megiddo, of finding a lexicographically optimal flow in a network with multiple sources and sinks, which is a special case of the problem considered here.