This note gives a characterization of the universal pair of bases of a pair of polymatroids as the nearest pair of bases with respect to a class of pseudo-distances including the Kullback-Leibler divergence. N. Megiddo considered the lexico-optimal flow problem in a multiterminal network N=(V,A,c;S’+,S’-) (V: vertex set, A: arc set, A: arc set, c: capacity, S’+: supply (source) vertices, S’-: demand (sink) vertices), which is to find a maximal flow such that the supply flow (s’+(ν)ℝν∈S’+) [resp., the demand flow (s’-(ν)ℝν∈S’-)] is as proportional as possible to a given weight vector. This problem is treated by S. Fujishige as a special case of the lexico-optimal base problem for a single polymatroid. This paper considers the problem of finding a maximal flow such that the supply flow s’+ and the demand flow s’- are as ‘near’ as possible (where a one-to-one correspondence between S’+ and S’- is assumed to be given), and generalizes it to the problem of finding a ‘nearest’ pair of bases of a pair of polymatroids. It is shown that the ‘nearest’ pair coincides with the universal pair if either of the following criteria is adopted: (1) the f-divergence (a generalization of the Kullback-Leibler divergence) between the bases should be minimized; (2) the vector consisting of the ratios of the corresponding components of the bases should be lexicographically maximized.
