Polyhedra with submodular support functions and their unbalanced simultaneous exchangeability
✍ Scribed by Kenji Kashiwabara; Takashi Takabatake
- Book ID
- 104294092
- Publisher
- Elsevier Science
- Year
- 2003
- Tongue
- English
- Weight
- 424 KB
- Volume
- 131
- Category
- Article
- ISSN
- 0166-218X
No coin nor oath required. For personal study only.
✦ Synopsis
We discuss matroid-likeness of polyhedra whose facets have non-01-vectors as their normal vectors. We propose, as a generalized class of submodular polyhedra, the class of down-monotone polyhedra whose support functions satisfy submodularity on non-negative vectors. The sets of feasible out ows of certain bipartite generalized networks are examples of such polyhedra. We prove that such polyhedra have certain unbalanced simultaneous exchangeability between two axes. This property gives a simple criterion of optimality for a linear objective function on these polyhedra. We also prove that this simultaneous exchangeability characterizes this generalized class of polyhedra, while a non-simultaneous version of this exchangeability does not.