Approximating the complexity measure of Vavasis-Ye algorithm is NP-hard

Levent Tuncel

This is a brief note. Given an $m \times n$ integer matrix $A$ of full row rank, we consider the problem of computing the maximum of $\|B^{-1}A\|_2$ where $B$ varies over all bases of $A$. This quantity appears in various places in the mathematical programming literature. More recently, logarithm of this number was the determining factor in the complexity bound of Vavasis and Ye's primal-dual interior-point algorithm. We prove that the problem of approximating this maximum norm, even within an exponential (in the dimension of $A$) factor, is NP-hard. Our proof is based on a closely related result of L. Khachiyan (On the complexity of approximating extremal determinants in matrices, {\em Journal of Complexity} 11 (1995) 138--153).

Research Report CORR 98-51, Department of Combinatorics and Optimization, Faculty of Mathematics, University of Waterloo, Waterloo, Ontario, Canada, November 1998.