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?


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.


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.