A special role of Boolean quadratic polytopes among other combinatorial polytopes

A. N. Maksimenko

Modelirovanie i analiz informacionnyh sistem, Tome 23 (2016) no. 1, pp. 23-40

Résumé

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 sense) than the families of polytopes 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 mentioned families. Article is published in the author's wording.

Détail

Keywords: NP-hard problems, affine reduction, faces of polytopes.