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.
Contact: [email protected]
![[PS]](../gif/PS.gif)
![[IP PAGE]](../gif/HOME.gif)
![[SEARCH AGAIN]](../gif/SEARCH.gif)