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


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.


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


  The deal is that Payday Loans Indiana online can save your time, nerves and make a solution of all your financial problems. It is strictly forbidden to administrate Cialis Soft online in conjunction with medications, which are composed of nitrates - antidepressants, drastic analgetic pills, sleeping pills, and others.