11 citations · 19 across the 10 of their papers we have counts for
11 papers
All 2-neighborly d-polytopes with at most d + 9 facets
Aleksandr N. Maksimenko, Dmitry V. Gribanov, Dmitry S. Malyshev
We give a complete enumeration of all 2-neighborly -polytopes with and less facets. All of them are realized as 0/1-polytopes, except a 6-polytope with 10 ve…
2-neighborly 0/1-polytopes of dimension 7
Aleksandr Maksimenko
We give a complete enumeration of all 2-neighborly 0/1-polytopes of dimension 7. There are 13 959 358 918 different 0/1-equivalence classes of such polytopes. They form 5 850 402 0…
Branch and bound algorithm for the traveling salesman problem is not a direct type algorithm
Aleksandr Maksimenko
In this paper, we consider the notion of a direct type algorithm introduced by V.A. Bondarenko in 1983. A direct type algorithm is a linear decision tree with some special properti…
On the minimum number of facets of a 2-neighborly polytope
Aleksandr Maksimenko
Let (respectively, ) be the minimal number of facets of a (simplicial) 2-neighborly -polytope with vertices, $v > d \ge 4…
Affine maps between quadratic assignment polytopes and subgraph isomorphism polytopes
Aleksandr Maksimenko
We consider two polytopes. The quadratic assignment polytope is the convex hull of the set of tensors , , where is the set of perm…
Boolean quadric polytopes are faces of linear ordering polytopes
Aleksandr Maksimenko
Let be a boolean quadric polytope, be a linear ordering polytope. It is shown that is linearly isomorphic to a face of .
On the family of 0/1-polytopes with NP-complete non-adjacency relation
Alexander Maksimenko
In 1995 T. Matsui considered a special family 0/1-polytopes for which the problem of recognizing the non-adjacency of two arbitrary vertices is NP-complete. In 2012 the author of t…
The lower bound for the number of facets of a k-neighborly d-polytope with d+3 vertices
Aleksandr Maksimenko
We have found the minimal difference between the number of facets and the number of vertices of a -neighborly -polytope for…
Complexity of LP in Terms of the Face Lattice
Aleksandr Maksimenko
Let be a finite set in . We consider the problem of optimizing linear function on , where is an input vector. We call it a problem . A prob…
A special role of Boolean quadratic polytopes among other combinatorial polytopes
Aleksandr Maksimenko
We consider several families of combinatorial polytopes associated with the following NP-complete problems: maximum cut, Boolean quadratic programming, quadratic linear ordering, q…
Small Extended Formulations for Cyclic Polytopes
Yuri Bogomolov, Samuel Fiorini, Aleksandr Maksimenko +1
We provide an extended formulation of size O(log n)^{\lfloor d/2 \rfloor} for the cyclic polytope with dimension d and n vertices (i,i^2,\ldots,i^d), i in [n]. First, we find an ex…