Contributed Session Wed.3.H 3013

Wednesday, 15:15 - 16:45 h, Room: H 3013

Cluster 2: Combinatorial optimization [...]

Polyhedra in combinatorial optimization


Chair: Shungo Koichi



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

Shungo Koichi
A note on ternary semimodular polyhedra


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.



Wednesday, 15:45 - 16:10 h, Room: H 3013, Talk 2

Aleksandr Maksimenko
The common face of some 0/1 polytopes with NP-complete nonadjacency relations


We consider so-called double covering polytopes (DCP).
In 1995, Matsui showed that the problem of checking nonadjacency on these polytopes is NP-complete.
We show that double covering polytopes are faces of the following polytopes: knapsack polytopes, set covering polytopes, cubic graph polytopes, 3-SAT polytopes, partial order polytopes, traveling salesman polytopes, and some others.
Thus, these families of polytopes inherit the property of NP-completness of nonadjacency relations from DCP.
We show also that the graph of a double covering polytope has superpolynomial clique number.
The same is true for the mentioned families of polytopes.



Wednesday, 16:15 - 16:40 h, Room: H 3013, Talk 3

Shanfei Li
The polyhedral relationship between the capacitated facility location polytope and its knapsack and single-node flow relaxations

Coauthor: Karen Aardal


The knapsack and single node flow polytopes, XK and XSNF respectively, are well-known relaxations of the capacitated facility location polytope XCFL. In earlier studies specific classes of facets for XK and XSNF have been proved to be facets also for XCFL, and the computational effectiveness of these classes have also been demonstrated for XCFL. In this presentation
we prove more general relationships between the polytopes XK, XSNF, and XCFL. We also prove results in the spirit of Goemans' worst-case comparison of valid inequalities.


  Online lending company provides a wide range of ways to get money by means of Tennessee Loans Online. One of the main advantages of Sovaldi is that it can be used by patients belonging to all 4 genotypes. Buy Sovaldi is a very strong drug, and as all of them, it has a number of side effects that can be caused.