APPROXIMATIONS TO SOLUTIONS TO SYSTEMS OF LINEAR INEQUALITIES

In this paper we consider a result of Hoffman [J. Res. Nat. Bur. Stand ., 49 (1952) pp. 263-265] about approximate solutions to systems of li near inequalities. We obtain a new representation for a corresponding Lipschitz bound via singular values. We also provide geometric represe ntations of these bounds via extreme points. The latter have been deve loped independently by Bergthaller and Singer [Linear Algebra Appl,, 1 69 (1992), pp, 111-129] and Li [Linear Algebra Appl., 187 (1993), pp. 15-40], but, our proofs are simpler. We obtain a particularly simple p roof of Hoffman's existence result which relies only on linear program ming duality.