Mobius Functions of Rooted Forests and Faigle-Kern's Dual Greedy Polyhedra

スポンサーリンク

概要

• 論文の詳細を見る

• A dual greedy polyhedron is defined by a sys-tem of linear inequalities, where the right-hand sides are given by a submodular function and the coefficients matrix is given by the incidence vectors of antichains of a rooted forest. Faigle and Kern introduced this concept, and showed that a dual greedy algorithm works for the linear program over dual greedy polyhedra. In this paper, we show that a dual greedy polyhedron is the iso-morphic image, of an ordinary submodular polyhedron under the Mobius function of the underlying rooted forest. This observation enables us to reduce linear optimization problems over dual greedy polyhedra to those over ordinary submodular polyhedra. We show a new max-min theorem for intersection of two dual greedy polyhedra as well.

• 社団法人電子情報通信学会の論文
• 2003-05-01

著者

• Ando Kazutoshi

  Department Of Systems Engineering Faculty Of Engineering Shizuoka University

関連論文

• Mobius Functions of Rooted Forests and Faigle-Kern's Dual Greedy Polyhedra

スポンサーリンク