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

Given an m x n integer matrix A of full row rank, we consider the problem o f computing the maximum of parallel to B-1 A parallel to(2) where B varies over all bases of A. This quantity appears in various places in the mathema tical programming literature. More recently, logarithm of this number was t he determining factor in the complexity bound of Vavasis and Ye's primal-du al interior-point algorithm. We prove that the problem of approximating thi s 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 [1].