For interior point methods of linear programming, what is the "L" in the computational complexity $\mathcal{O}(n^3 L)$?

Question

My question is about interior point methods of linear programming. Suppose the constraint matrix $A$ has $m$ rows and $n$ columns, and $m<n$. The state-of-the-art methods, like primal dual interior point method, usually have iteration $\mathcal{O}(\sqrt{n}L)$ and arithmetic operations $\mathcal{O}(n^3 L)$. I am concerned with expressing $L$ in terms of $m$ and $n$.

However, I found two definition of $L$. One is given by Pravin M. VAIDYA, in the paper "an algorithm for linear programming which requires $\mathcal{O}(((m + n)n^2+ (m + n)^{1.5})L)$ arithmetic operations". In that paper, $L$ is defined as the logarithm the largest absolute value of the determinant of any square submatrix of $A$, plus some small terms. This definition also appears in the classic paper of N.Karmarkar, which is "A new polynomial-time algorithm for linear programming".

Another definition is more common. It simply says that $L$ is the total number of bits of the input. This definition is rather safe, since the order of the first definition is bounded by the order of this definition.

I am inclined to adopt the first definition, since it gives a better bound in my problem. But, it seems that it is less used by researchers, and I wonder if it is OK to use the first one?

Answer 1

Yes, as you say, both usages occur in the literature, with "total number of bits in the input" being more prevalent in interior point papers. But I guess Vaidya has noticed that one can be more careful about things. By the way, I believe the fastest known algorithm for linear programming is from Vaidya's paper "Speeding-up linear programming using fast matrix multiplication". The running time is $O((m+n)^{1.5} n L)$ arithmetic operations, where $L$ is again the more complicated quantity, roughly the log of the max subdeterminant.