Mobius Functions of Rooted Forests and Faigle-Kern's Dual Greedy Polyhedra
Summary :
A dual greedy polyhedron is defined by a system 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 isomorphic 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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E86-A No.5 pp.995-999
- Publication Date
- 2003/05/01
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Kazutoshi ANDO, "Mobius Functions of Rooted Forests and Faigle-Kern's Dual Greedy Polyhedra" in IEICE TRANSACTIONS on Fundamentals,
vol. E86-A, no. 5, pp. 995-999, May 2003, doi: .
Abstract: A dual greedy polyhedron is defined by a system 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 isomorphic 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e86-a_5_995/_p
Copy
@ARTICLE{e86-a_5_995,
author={Kazutoshi ANDO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Mobius Functions of Rooted Forests and Faigle-Kern's Dual Greedy Polyhedra},
year={2003},
volume={E86-A},
number={5},
pages={995-999},
abstract={A dual greedy polyhedron is defined by a system 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 isomorphic 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.},
keywords={},
doi={},
ISSN={},
month={May},}
Copy
TY - JOUR
TI - Mobius Functions of Rooted Forests and Faigle-Kern's Dual Greedy Polyhedra
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 995
EP - 999
AU - Kazutoshi ANDO
PY - 2003
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E86-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2003
AB - A dual greedy polyhedron is defined by a system 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 isomorphic 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.
ER -
English
