A classical theorem by Block and Levin says that certain variants of the relaxation method for solving systems of linear inequalities produce bounded sequences of intermediate solutions even when running on inconsistent input data. Using a new approach, we prove a more general version of this result and answer an old open problem of quantifying the bounds as a function of the input data.
Citation
NA 03/18 Oxford University Computing Laboratory; Wolfson Building; Parks Road; Oxford, OX1 3QD; United Kingdom