Primal Dual Algorithms for the Lexicographically Optimal Base of a Submodular Polyhedron and Its Relation to a Poset Greedoid

ＰｒｉｍａｌＤｕａｌＡｌｇｏｒｉｔｈｍｓｆｏｒｔｈｅＬｅｘｉｃｏｇｒａｐｈｉｃａｌｌｙＯｐｔｉｍａｌＢａｓｅｏｆａＳｕｂｍｏｄｕｌａｒＰｏｌｙｈｅｄｒｏｎａｎｄＩｔｓＲｅｌａｔｉｏｎｔｏａＰｏｓｅｔＧｒｅｅｄｏｉｄＫａｋｕｚｏＩｗａｍｕｒａ（Ｓａｎｂ...

Primal Dual Algorithms for the Lexicographically Optimal Base of a Submodular Polyhedron and Its Relation to a Poset Greedoid

We show that for a submodular polyhedron and its dual supermodular polyhedron the exists a unique lexicographically optimal base with respect to a weight vector and they coincide.We also present a dual algorithm to get the lexicograpllically optima base of a submodular polyhedron which works on its dula superlnodular polyhedron.This dual algorithm completely agrees to the algorithm of Morton,G.and von Tandow,R.and Ringwald,K.1985],where their underlying distributive lattice is a chaill poset greedoid.Finally we show that finding the lesicographically optimal base of a submodular system is essentially equivalent to finding the lexicographically optimal base of a simple submodular system,where its underlying distributive lattice is a poset greedoid.This fact.indicates the importance of greedoids in a further development of submodular system theory.