This article is cited in
3 papers
A special role of Boolean quadratic polytopes among other combinatorial polytopes
A. N. Maksimenko P.G. Demidov Yaroslavl State University, Sovetskaya str., 14, Yaroslavl, 150000, Russia
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 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.
Keywords:
NP-hard problems, affine reduction, faces of polytopes.
UDC:
519.854.33 Received: 15.11.2015
Language: English
DOI:
10.18255/1818-1015-2016-1-23-40
Fulltext:
PDF file (605 kB)