This article is cited in 2 scientific papers (total in 2 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
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.
NP-hard problems, affine reduction, faces of polytopes.
PDF file (605 kB)
A. N. Maksimenko, “A special role of Boolean quadratic polytopes among other combinatorial polytopes”, Model. Anal. Inform. Sist., 23:1 (2016), 23–40
Citation in format AMSBIB
\paper A special role of Boolean quadratic polytopes among other combinatorial polytopes
\jour Model. Anal. Inform. Sist.
Citing articles on Google Scholar:
Related articles on Google Scholar:
This publication is cited in the following articles:
A. N. Maksimenko, “On a family of 0/1-polytopes with an NP-complete criterion for vertex nonadjacency relation”, Discrete Math. Appl., 29:1 (2019), 7–14
A. N. Maksimenko, “Bulev kvadratichnyi mnogogrannik yavlyaetsya granyu mnogogrannika lineinykh poryadkov”, Sib. elektron. matem. izv., 14 (2017), 640–646
|Number of views:|