A linear program (LP)

\begin{alignat}{1} & \min_{x} {c}^{T}x, \\ \mathrm{s.t.} & \quad Ax = b, \\ & x \geq 0. \end{alignat}

is called combinatorial if the size of entries of matrix $A \in \mathbb{R}^{m \times n}$ is bounded by a polynomial of dimension of the LP. (See Eva Tardós, "A strongly polynomial algorithm to solve combinatorial linear programs", Operations Research (1985)) The size of a rational number is described as the length of its binary representation.

It seems as though any entry size is a polynomial of the LP dimension. In other words, size($a_{ij}$) = size($a_{ij}$) * $m^0$ $n^0$ where size of LP is $m\times n$. So it seems like any LP is combinatorial. Why isn't this statement true?


This is certainly true for any individual problem, but this sort of statement is typically made about a family of LPs. In that case, the dimensions of the matrix and the entries of the matrix are typically expressed in terms of other parameters $\theta = (\theta_1, \theta_2, \dotsc, \theta_k)$ for some $k \geq 1$ - i.e., we have $n(\theta)$ and $m(\theta)$. If the size of each $A_{ij}$ can be given as an expression (in $\theta$) that is bounded by a polynomial in the expressions $n(\theta)$ and $m(\theta)$, then we have a combinatorial LP.

Your argument is somewhat similar to saying, "Once I am given a graph on $n$ vertices, $n$ is a constant, so I can enumerate all $n!$ tours in constant time. Therefore I can solve the travelling salesman problem on that graph in polynomial time. But this holds for every graph. Hence P=LP."


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.