Wednesday, 15:15 - 15:40 h, Room: H 3013

 

Shungo Koichi
A note on ternary semimodular polyhedra

 

Abstract:
A ternary semimodular polyhedron associated with a submodular function on {0, ± 1} vectors was introduced by Fujishige in 1984, and it is not necessary integral even if the submodular function is integer-valued. However, it is known that the polyhedron has a nice property that corresponds to a laminarity property of the (standard) submodular polyhedra. In this paper, we give a slightly different type of polyhedron associated with a submodular function on {0, ± 1} vectors,
and show that it also has the nice property as above and moreover, due to the nice property,
it is quarter-integral if the submodular function is integer-valued. In addition, this paper proposes a variant of a submodular function on {0, ± 1} that preserves the quarter-integrality of the newly-defined associated polyhedron. The proof uses the result by Karzanov in 2007 concerning the integrality of the intersection of two integer
bisubmodular polyhedra. Our results may be applicable to the multicommodity flow problem,
which is our motivation.

 

Talk 1 of the contributed session Wed.3.H 3013
"Polyhedra in combinatorial optimization" [...]
Cluster 2
"Combinatorial optimization" [...]

 

  personal loans. Of course, the choice is not that easy, as there exist great number of different preparations. Notwithstanding, Cialis Online is the one that definitely differs from all other products.