A method for the parametric center problem, with a strictly monotone polynomial-time algorithm for linear programming

Given a system of linear inequalities and equalities , where the right-hand sides are parametrically deformed over the scalar t, the parametric center problem is to trace the parametric family of approximate solutions to the centre problems P(t), where P(t) is the problem: maximize subject to and . The authors present an algorithm for tracing the parametric family of solutions over some given range. At the kth iterate of the algorithm, the point is an approximate solution to the center problem P(t ^k) (in an appropriate measure of approximation). The value of t ^k is increased to , and a Newton step is used to generate which is an approximate solution to the center problem . The sequence of values of t exhibit at least one of the following geometric rates of change: