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

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

0.00 Avg rating0 Votes
Article ID: iaor20002412
Country: Germany
Volume: 86
Issue: 1
Start Page Number: 219
End Page Number: 223
Publication Date: Jan 1999
Journal: Mathematical Programming
Authors:
Abstract:

Given an m × 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.

Reviews

Required fields are marked *. Your email address will not be published.