The Quadratic Assignment Problem (QAP) is a well-known NP-hard problem that is equivalent to optimizing a linear objective function over the QAP polytope. The QAP polytope with parameter $n$ - qappolytope{n} - is defined as the convex hull of rank-$1
$ matrices $xx^T$ with $x$ as the vectorized $ntimes n$ permutation matrices. In this paper we consider all the known exponential-sized families of facet-defining inequalities of the QAP-polytope. We describe a new family of valid inequalities that we show to be facet-defining. We also show that membership testing (and hence optimizing) over some of the known classes of inequalities is coNP-complete. We complement our hardness results by showing a lower bound of $2^{Omega(n)}$ on the extension complexity of all relaxations of qappolytope{n} for which any of the known classes of inequalities are valid.
It can be shown that each permutation group $G sqsubseteq S_n$ can be embedded, in a well defined sense, in a connected graph with $O(n+|G|)$ vertices. Some groups, however, require much fewer vertices. For instance, $S_n$ itself can be embedded in t
he $n$-clique $K_n$, a connected graph with n vertices. In this work, we show that the minimum size of a context-free grammar generating a finite permutation group $G sqsubseteq S_n$ can be upper bounded by three structural parameters of connected graphs embedding $G$: the number of vertices, the treewidth, and the maximum degree. More precisely, we show that any permutation group $G sqsubseteq S_n$ that can be embedded into a connected graph with $m$ vertices, treewidth k, and maximum degree $Delta$, can also be generated by a context-free grammar of size $2^{O(kDeltalogDelta)}cdot m^{O(k)}$. By combining our upper bound with a connection between the extension complexity of a permutation group and the grammar complexity of a formal language, we also get that these permutation groups can be represented by polytopes of extension complexity $2^{O(k Deltalog Delta)}cdot m^{O(k)}$. The above upper bounds can be used to provide trade-offs between the index of permutation groups, and the number of vertices, treewidth and maximum degree of connected graphs embedding these groups. In particular, by combining our main result with a celebrated $2^{Omega(n)}$ lower bound on the grammar complexity of the symmetric group $S_n$ we have that connected graphs of treewidth $o(n/log n)$ and maximum degree $o(n/log n)$ embedding subgroups of $S_n$ of index $2^{cn}$ for some small constant $c$ must have $n^{omega(1)}$ vertices. This lower bound can be improved to exponential on graphs of treewidth $n^{varepsilon}$ for $varepsilon<1$ and maximum degree $o(n/log n)$.
Linear programming is a powerful method in combinatorial optimization with many applications in theory and practice. For solving a linear program quickly it is desirable to have a formulation of small size for the given problem. A useful approach for
this is the construction of an extended formulation, which is a linear program in a higher dimensional space whose projection yields the original linear program. For many problems it is known that a small extended formulation cannot exist. However, most of these problems are either $mathsf{NP}$-hard (like TSP), or only quite complicated polynomial time algorithms are known for them (like for the matching problem). In this work we study the minimum makespan problem on identical machines in which we want to assign a set of $n$ given jobs to $m$ machines in order to minimize the maximum load over the machines. We prove that the canonical formulation for this problem has extension complexity $2^{Omega(n/log n)}$, even if each job has size 1 or 2 and the optimal makespan is 2. This is a case that a trivial greedy algorithm can solve optimally! For the more powerful configuration integer program, we even prove a lower bound of $2^{Omega(n)}$. On the other hand, we show that there is an abstraction of the configuration integer program admitting an extended formulation of size $f(text{opt})cdot text{poly}(n,m)$. In addition, we give an $O(log n)$-approximate integral formulation of polynomial size, even for arbitrary processing times and for the far more general setting of unrelated machines.
For each integer $n$ we present an explicit formulation of a compact linear program, with $O(n^3)$ variables and constraints, which determines the satisfiability of any 2SAT formula with $n$ boolean variables by a single linear optimization. This con
trasts with the fact that the natural polytope for this problem, formed from the convex hull of all satisfiable formulas and their satisfying assignments, has superpolynomial extension complexity. Our formulation is based on multicommodity flows. We also discuss connections of these results to the stable matching problem.
It is an open question whether the linear extension complexity of the Cartesian product of two polytopes P, Q is the sum of the extension complexities of P and Q. We give an affirmative answer to this question for the case that one of the two polytopes is a pyramid.
In this article we undertake a study of extension complexity from the perspective of formal languages. We define a natural way to associate a family of polytopes with binary languages. This allows us to define the notion of extension complexity of fo
rmal languages. We prove several closure properties of languages admitting compact extended formulations. Furthermore, we give a sufficient machine characterization of compact languages. We demonstrate the utility of this machine characterization by obtaining upper bounds for polytopes for problems in nondeterministic logspace; lower bounds in streaming models; and upper bounds on extension complexities of several polytopes.
Let $G$ be a graph on $n$ vertices and $mathrm{STAB}_k(G)$ be the convex hull of characteristic vectors of its independent sets of size at most $k$. We study extension complexity of $mathrm{STAB}_k(G)$ with respect to a fixed parameter $k$ (analogous
ly to, e.g., parameterized computational complexity of problems). We show that for graphs $G$ from a class of bounded expansion it holds that $mathrm{xc}(mathrm{STAB}_k(G))leqslant mathcal{O}(f(k)cdot n)$ where the function $f$ depends only on the class. This result can be extended in a simple way to a wide range of similarly defined graph polytopes. In case of general graphs we show that there is {em no function $f$} such that, for all values of the parameter $k$ and for all graphs on $n$ vertices, the extension complexity of $mathrm{STAB}_k(G)$ is at most $f(k)cdot n^{mathcal{O}(1)}.$ While such results are not surprising since it is known that optimizing over $mathrm{STAB}_k(G)$ is $FPT$ for graphs of bounded expansion and $W[1]$-hard in general, they are also not trivial and in both cases stronger than the corresponding computational complexity results.
We consider the convex hull $P_{varphi}(G)$ of all satisfying assignments of a given MSO formula $varphi$ on a given graph $G$. We show that there exists an extended formulation of the polytope $P_{varphi}(G)$ that can be described by $f(|varphi|,tau
)cdot n$ inequalities, where $n$ is the number of vertices in $G$, $tau$ is the treewidth of $G$ and $f$ is a computable function depending only on $varphi$ and $tau.$ In other words, we prove that the extension complexity of $P_{varphi}(G)$ is linear in the size of the graph $G$, with a constant depending on the treewidth of $G$ and the formula $varphi$. This provides a very general yet very simple meta-theorem about the extension complexity of polytopes related to a wide class of problems and graphs. As a corollary of our main result, we obtain an analogous result % for the weaker MSO$_1$ logic on the wider class of graphs of bounded cliquewidth. Furthermore, we study our main geometric tool which we term the glued product of polytopes. While the glued product of polytopes has been known since the 90s, we are the first to show that it preserves decomposability and boundedness of treewidth of the constraint matrix. This implies that our extension of $P_varphi(G)$ is decomposable and has a constraint matrix of bounded treewidth; so far only few classes of polytopes are known to be decomposable. These properties make our extension useful in the construction of algorithms.
It is known that the extension complexity of the TSP polytope for the complete graph $K_n$ is exponential in $n$ even if the subtour inequalities are excluded. In this article we study the polytopes formed by removing other subsets $mathcal{H}$ of fa
cet-defining inequalities of the TSP polytope. In particular, we consider the case when $mathcal{H}$ is either the set of blossom inequalities or the simple comb inequalities. These inequalities are routinely used in cutting plane algorithms for the TSP. We show that the extension complexity remains exponential even if we exclude these inequalities. In addition we show that the extension complexity of polytope formed by all comb inequalities is exponential. For our proofs, we introduce a subclass of comb inequalities, called $(h,t)$-uniform inequalities, which may be of independent interest.
A perfect matching in an undirected graph $G=(V,E)$ is a set of vertex disjoint edges from $E$ that include all vertices in $V$. The perfect matching problem is to decide if $G$ has such a matching. Recently Rothvo{ss} proved the striking result that
the Edmonds matching polytope has exponential extension complexity. Here for each $n=|V|$ we describe a perfect matching polytope that is different from Edmonds polytope and define a weaker notion of extended formulation. We show that the new polytope has a weak extended formulation (WEF) $Q$ of polynomial size. For each graph $G$ with $n$ vertices we can readily construct an objective function so that solving the resulting linear program over $Q$ decides whether or not $G$ has a perfect matching. The construction is uniform in the sense that, for each $n$, a single polytope is defined for the class of all graphs with $n$ nodes. The method extends to solve poly time optimization problems, such as the weighted matching problem. In this case a logarithmic (in the weight of the optimum solution) number of optimizations are made over the constructed WEF. The method described in the paper involves construction of a compiler that converts an algorithm given in a prescribed pseudocode into a polytope. It can therefore be used to construct a polytope for any decision problem in {bf P} which can be solved by a given algorithm. Compared with earlier results of Dobkin-Lipton-Reiss and Valiant our method allows the construction of explicit linear programs directly from algorithms written for a standard register model, without intermediate transformations. We apply our results to obtain polynomial upper bounds on the non-negative rank of certain slack matrices related to membership testing of languages in {bf P/Poly}.
