What are the best possible time/error tradeoffs for approximate solution of linear programs?
Perhaps this reference will be relevant to your question.

Grigoriadis M., Khachiyan L. A sublinear randomized approximation algorithm to matrix games// Oper. Res. Lett. 1995. V. 18. No 2. P. 53-58.

The algorithm therein is 1) randomized 2) the error is ADDITIVE, but 3) is sublinear (you need to check only tiny fraction of the input to find solutiom with high probability).

Sergey