Complexity of LP in Terms of the Face Lattice

Abstract

Let $X$ be a finite set in $Z^d$. We consider the problem of optimizing linear function $f(x)=c^{T}x$ on $X$, where $c\in Z^d$ is an input vector. We call it a problem $X$. A problem $X$ is related with linear program $\underset{x\in P}{\max }f(x)$, where polytope $P$ is a convex hull of $X$. The key parameters for evaluating the complexity of a problem $X$ are the dimension $d$, the cardinality $|X|$, and the encoding size $S(X)={\log }_2\left(\underset{x\in X}{\max }\Vert x{\Vert }_{\infty }\right)$. We show that if the (time and space) complexity of some algorithm $A$ for solving a problem $X$ is defined only in terms of combinatorial structure of $P$ and the size $S(X)$, then for every $d$ and $n$ there exists polynomially (in $d$, $\log n$, and $S$) solvable problem $Y$ with $\dim Y=d$, $|Y|=n$, such that the algorithm $A$ requires exponential time or space for solving $Y$.

11 pages

References in corpus (3)

• A Short Proof that the Extension Complexity of the Correlation Polytope Grows Exponentially
• Extended Formulations in Combinatorial Optimization
• Small Extended Formulations for Cyclic Polytopes