A special role of Boolean quadratic polytopes among other combinatorial polytopes

Abstract

We consider several families of combinatorial polytopes associated with the following NP-complete problems: maximum cut, Boolean quadratic programming, quadratic linear ordering, quadratic assignment, set partition, set packing, stable set, 3-assignment. For comparing two families of polytopes we use the following method. We say that a family $P$ is affinely reduced to a family $Q$ if for every polytope $p\in P$ there exists $q\in Q$ such that $p$ is affinely equivalent to $q$ or to a face of $q$, where $\dim q=O((\dim p{)}^k)$ for some constant $k$. Under this comparison the above-mentioned families are splitted into two equivalence classes. We show also that these two classes are simpler (in the above sence) than the families of poytopes of the following problems: set covering, traveling salesman, 0-1 knapsack problem, 3-satisfiability, cubic subgraph, partial ordering. In particular, Boolean quadratic polytopes appear as faces of polytopes in every of the mentioned families.

16 pages

References in corpus (3)

• Extended Formulations in Combinatorial Optimization
• On the extension complexity of combinatorial polytopes
• A special role of Boolean quadratic polytopes among other combinatorial polytopes

Cited by in corpus (5)

• A special role of Boolean quadratic polytopes among other combinatorial polytopes
• The lower bound for the number of facets of a k-neighborly d-polytope with d+3 vertices
• Some characteristics of the simple Boolean quadric polytope extension
• On the minimum number of facets of a 2-neighborly polytope
• On the family of 0/1-polytopes with NP-complete non-adjacency relation