Minimizing a submodular function arising from a concave function

We consider a class of submodular functions on distributive lattices that a re defined in terms of concave functions and modular functions. The minimiz ation of such a submodular function is made in time required for a max-flow computation on an associated network by means of the parametric max-flow a lgorithm of Gallo, Grigoriadis and Tarjan. The problem is closely related t o the classic majorization and the majorization on posets. As an applicatio n of the parametric approach, we improve the time complexity of a capacity scaling algorithm for the submodular flow problem. We also discuss a genera lization and its relation to the principal partition or the lexicographical ly optimal base of a submodular system. (C) 1999 Elsevier Science B.V. All rights reserved.