Optimization with additional variables and constraints

Norton, Plotkin and Tardos proved that-loosely spoken, an LP problem is solvable in time O(Tqk+1) if deleting k fixed columns or rows, we obtain a problem which can be solved by an algorithm that makes at most T steps and q comparisons. This paper improves this running time to O(Tqk).