Consolidation for compact constraints and Kendall tau LP decodable permutation codes

Invented in the 1960s, permutation codes have reemerged in recent years as a topic of great interest because of properties making them attractive for certain modern technological applications, especially flash memory. In 2011 a polynomial time algorithm called linear programming (LP) decoding was introduced for a class of permutation codes where the feasible set of codewords was a subset of the vertex set of a code polytope. In this paper we investigate a new class of linear constraints for matrix polytopes with no fractional vertices through a new concept called “consolidation.” We then introduce a necessary and sufficient condition for which LP decoding methods, originally designed for the Euclidean metric, may be extended to provide an efficient decoding algorithm for permutation codes with the Kendall tau metric.     

Primal—Dual Methods for Vertex and Facet Enumeration

Every convex polytope can be represented as the intersection of a finite set of halfspaces and as the convex hull of its vertices. Transforming from the halfspace (resp. vertex) to the vertex (resp. halfspace) representation is called vertex enumeration (resp. facet enumeration ). An open question is whether there is an algorithm for these two problems (equivalent by geometric duality) that is polynomial in the input size and the output size. In this paper we extend the known polynomially solvable classes of polytopes by looking at the dual problems. The dual problem of a vertex (resp. facet) enumeration problem is the facet (resp. vertex) enumeration problem for the same polytope where the input and output are simply interchanged. For a particular class of polytopes and a fixed algorithm, one transformation may be much easier than its dual. In this paper we propose a new class of algorithms that take advantage of this phenomenon. Loosely speaking, primal—dual algorithms use a solution to the easy direction as an oracle to help solve the seemingly hard direction. Received July 31, 1997, and in revised form March 8, 1998.     

Covers ℘ for Abstract Regular Polytopes \mathcal {Q} such that \mathcal{Q}=\mathcal{P}/\mathbf{Z}_{p}^{k}

One key problem in the theory of abstract polytopes is the so-called amalgamation problem. In its most general form, this is the problem of characterising the polytopes with given facets  $\mathcal {K}$ and vertex figures ?. The first step in solving it for particular  $\mathcal{K}$ and ? is to find the universal such polytope, which covers all the others. This article explains a construction that may be attempted on an arbitrary polytope ?, which often yields an infinite family of finite polytopes covering ? and sharing its facets and vertex figures. The existence of such an infinite family proves that the universal polytope is infinite; alternatively, the construction can produce an explicit example of an infinite polytope of the desired type. An algorithm for attempting the construction is explained, along with sufficient conditions for it to work. The construction is applied to a few  $\mathcal{K}$ and ? for which it was previously not known whether or not the universal polytope was infinite, or for which only a finite number of finite polytopes was previously known. It is conjectured that the construction is quite broadly applicable.     

Box-inequalities for quadratic assignment polytopes

Linear Programming based lower bounds have been considered both for the general as well as for the symmetric quadratic assignment problem several times in the recent years. Their quality has turned out to be quite good in practice. Investigations of the polytopes underlying the corresponding integer linear programming formulations (the non-symmetric and the symmetric quadratic assignment polytope) have been started during the last decade [34, 31, 21, 22]. They have lead to basic knowledge on these polytopes concerning questions like their dimensions, affine hulls, and trivial facets. However, no large class of (facet-defining) inequalities that could be used in cutting plane procedures had been found. We present in this paper the first such class of inequalities, the box inequalities, which have an interesting origin in some well-known hypermetric inequalities for the cut polytope. Computational experiments with a cutting plane algorithm based on these inequalities show that they are very useful with respect to the goal of solving quadratic assignment problems to optimality or to compute tight lower bounds. The most effective ones among the new inequalities turn out to be indeed facet-defining for both the non-symmetric as well as for the symmetric quadratic assignment polytope. Received: April 17, 2000 / Accepted: July 3, 2001?Published online September 3, 2001     

Parameter spaces of separating hyperplanes

Every pair of relatively disjoint polytopes is dual to the parameter space of all their separating hyperplanes, which is also a polytope. For a polytope whose interior is disjoint from the relative interior of another polytope, the parameter space of all separating hyperplanes is a polytope of the same dimension. One face of this parameter space parametrizes the separating hyperplanes that also simultaneously support both polytopes. A separating hyperplane corresponds to a vertex of this face if and only if no other hyperplanes support the polytopes at the same intersection points. If all the vertices of the polytopes have all their coordinates in an ordered field, then the same results and their proofs hold with the same ordered field.     

Adjacency on the order polytope with applications to the theory of fuzzy measures

In this paper we study the adjacency structure of the order polytope of a poset. For a given poset, we determine whether two vertices in the corresponding order polytope are adjacent. This is done through filters in the original poset. We also prove that checking adjacency between two vertices can be done in quadratic time on the number of elements of the poset. As particular cases of order polytopes, we recover the adjacency structure of the set of fuzzy measures and obtain it for the set of p-symmetric measures for a given indifference partition; moreover, we show that the set of p-symmetric measures can be seen as the order polytope of a quotient set of the poset leading to fuzzy measures. From this property, we obtain the diameter of the set of p-symmetric measures. Finally, considering the set of p-symmetric measures as the order polytope of a direct product of chains, we obtain some other properties of these measures, as bounds on the volume and the number of vertices on certain cases.     

An Adaptive Algorithm for Vector Partitioning

The vector partition problem concerns the partitioning of a set A of n vectors in d-space into p parts so as to maximize an objective function c which is convex on the sum of vectors in each part. Here all parameters d, p, n are considered variables. In this paper, we study the adjacency of vertices in the associated partition polytopes. Using our adjacency characterization for these polytopes, we are able to develop an adaptive algorithm for the vector partition problem that runs in time O(q(L)v) and in space O(L), where q is a polynomial function, L is the input size and v is the number of vertices of the associated partition polytope. It is based on an output-sensitive algorithm for enumerating all vertices of the partition polytope. Our adjacency characterization also implies a polynomial upper bound on the combinatorial diameter of partition polytopes. We also establish a partition polytope analogue of the lower bound theorem, indicating that the output-sensitive enumeration algorithm can be far superior to previously known algorithms that run in time polynomial in the size of the worst-case output.     

Ricci Positive Metrics on the Moment-Angle Manifolds

In this paper, the authors consider the problem of which (generalized) moment-angle manifolds admit Ricci positive metrics. For a simple polytope $P$, the authors can cut off one vertex $v$ of $P$ to get another simple polytope $P_{v}$, and prove that if the generalized moment-angle manifold corresponding to $P$ admits a Ricci positive metric, the generalized moment-angle manifold corresponding to $P_{v}$ also admits a Ricci positive metric. For a special class of polytope called Fano polytopes, the authors prove that the moment-angle manifolds corresponding to Fano polytopes admit Ricci positive metrics. Finally some conjectures on this problem are given.     

Equidecomposable and weakly neighborly polytopes

A polytope is equidecomposable if all its triangulations have the same face numbers. For an equidecomposable polytope all minimal affine dependencies have an equal number of positive and negative coefficients. A subclass consists of the weakly neighborly polytopes, those for which every set of vertices is contained in a face of at most twice the dimension as the set. Theh-vector of every triangulation of a weakly neighborly polytope equals theh-vector of the polytope itself. Combinatorial properties of this class of polytopes are studied. Gale diagrams of weakly neighborly polytopes with few vertices are characterized in the spirit of the known Gale diagram characterization of Lawrence polytopes, a special class of weakly neighborly polytopes.     

Integer Partitions from the Polyhedral Point of View

We characterize integer partitions that are convex combinations of two partitions, which connects vertices of the partition polytopes with Sidon sets and sum-free sets. We prove that all vertices of the partition polytope can be generated from a subset of support vertices with the use of two operations of merging parts. Application of either operation results in an adjacent vertex. We present also some numerical data on vertices.     

The travelling salesman problem and a class of polyhedra of diameter two

A class of polytopes is defined which includes the polytopes related to the assignment problem, the edge-matching problem on complete graphs, the multi-dimensional assignment problem, and many other set partitioning problems. Modifying some results due to Balas and Padberg, we give a constructive proof that the diameter of these polytopes is less than or equal to two. This result generalizes a result obtained by Balinski and Rusakoff in connection with the assignment problem.Furthermore, it is shown that the polytope associated with the travelling salesman problem has a diameter less than or equal to two. A weaker form of the Hirsch conjecture is also shown to be true for this polytope.Paper presented at the 8^th International Symposium on Mathematical Programming, Stanford, August, 1973.The research underlying this paper was done while both authors were Research Fellows at the International Institute of Management, Berlin, West Germany.     

Linear time approximation of 3D convex polytopes

We develop algorithms for the approximation of a convex polytope in by polytopes that are either contained in it or containing it, and that have fewer vertices or facets, respectively. The approximating polytopes achieve the best possible general order of precision in the sense of volume-difference. The running time is linear in the number of vertices or facets.     

Perturbation of transportation polytopes

We describe a perturbation method that can be used to reduce the problem of finding the multivariate generating function (MGF) of a non-simple polytope to computing the MGF of simple polytopes. We then construct a perturbation that works for any transportation polytope. We apply this perturbation to the family of central transportation polytopes of order $kn\times n$, and obtain formulas for the MGFs of the feasible cone of each vertex of the polytope and the MGF of the polytope. The formulas we obtain are enumerated by combinatorial objects. A special case of the formulas recovers the results on Birkhoff polytopes given by the author and De Loera and Yoshida. We also recover the formula for the number of maximum vertices of transportation polytopes of order $kn\times n$.     

On separation and adjacency problems for perfectly matchable subgraph polytopes of a graph

A subgraph F of graph G is called a perfectly matchable subgraph if F contains a set of independent edges convering all the vertices in F. The convex hull of the incidence vectors of perfectly matchable subgraphs of G is a 0–1 polytope. We characterize the adjacency of vertices on such polytopes. We also show that when G is bipartite, the separation problem for such polytones can be solved by maximum flow algorithms.     

Stable multi-sets

In this paper we introduce a generalization of stable sets: stable multi-sets. A stable multi-set is an assignment of integers to the vertices of a graph, such that specified bounds on vertices and edges are not exceeded. In case all vertex and edge bounds equal one, stable multi-sets are equivalent to stable sets.  For the stable multi-set problem, we derive reduction rules and study the associated polytope. We state necessary and sufficient conditions for the extreme points of the linear relaxation to be integer. These conditions generalize the conditions for the stable set polytope. Moreover, the classes of odd cycle and clique inequalities for stable sets are generalized to stable multi-sets and conditions for them to be facet defining are determined.  The study of stable multi-sets is initiated by optimization problems in the field of telecommunication networks. Stable multi-sets emerge as an important substructure in the design of optical networks. Received: February 14, 2001/Revised version: September 7, 2001     

Complexity of combinatorial optimization problems in terms of face lattices of associated polytopes

This paper deals with the following question: Can combinatorial properties of polytopes help in finding an estimate for the complexity of the corresponding optimization problem? Sometimes, these key characteristics of complexity were the number of hyperfaces of the polytope, diameter and clique number of the graph of the polytope, the rectangle covering number of the vertex-facet incidence matrix, and some other characteristics. In this paper, we provide several families of polytopes for which the above-mentioned characteristics differ significantly from the real computational complexity of the corresponding optimization problems. In particular, we give two examples of discrete optimization problem whose polytopes are combinatorially equivalent and they have the same lengths of the binary representation of the coordinates of the polytope vertices. Nevertheless, the first problem is solvable in polynomial time, while the second problem has exponential complexity.     

Gaps in the numbers of vertices of cubical polytopes,I

A cubical polytope is a convex polytope of which very facet is a combinatorial cube. We ask for the numbers which occur as vertex numbers ofd-dimensional cubical polytopes, and we show, as a first step, that every cubicald-polytope for evend≥4 has an even number of vertices.     

Self-Duality of Polytopes and its Relations to Vertex Enumeration and Graph Isomorphism

We study the complexity of determining whether a polytope given by its vertices or facets is combinatorially isomorphic to its polar dual. We prove that this problem is Graph Isomorphism hard, and that it is Graph Isomorphism complete if and only if Vertex Enumeration is Graph Isomorphism easy. To the best of our knowledge, this is the first problem that is not equivalent to Vertex Enumeration and whose complexity status has a non-trivial impact on the complexity of Vertex Enumeration irrespective of whether checking Self-duality turns out to be strictly harder than Graph Isomorphism or equivalent to Graph Isomorphism. The constructions employed in the proof yield a class of self-dual polytopes that are interesting on their own. In particular, this class of self-dual polytopes has the property that the facet-vertex incident matrix of the polytope is transposable if and only if the matrix is symmetrizable as well. As a consequence of this construction, we also prove that checking self-duality of a polytope, given by its facet-vertex incidence matrix, is Graph Isomorphism complete, thereby answering a question of Kaibel and Schwartz.     

Minimal Ellipsoid Circumscribing a Polytope Defined by a System of Linear Inequalities

In this paper, we will propose algorithms for calculating a minimal ellipsoid circumscribing a polytope defined by a system of linear inequalities. If we know all vertices of the polytope and its cardinality is not very large, we can solve the problem in an efficient manner by a number of existent algorithms. However, when the polytope is defined by linear inequalities, these algorithms may not work since the cardinality of vertices may be huge. Based on a fact that vertices determining an ellipsoid are only a fraction of these vertices, we propose algorithms which iteratively calculate an ellipsoid which covers a subset of vertices. Numerical experiment shows that these algorithms perform well for polytopes of dimension up to seven.