Using separation algorithms in fixed dimension
Carolyn H. Norton, Serge A. Plotkin, Éva Tardos · 1990
Consider a convex set in d dimensions. Assume that we are given a separation subroutine which, given a point, tells us whether this point is in the set. Moreover, if the point is not in the set, the subroutine separates the point from the set by a hyperplane. We show that if d is fixed and the separation subroutine is linear in the input vector, this implies that one can optimize a linear objective function over the convex set in time polynomial in the number of arithmetic operations used by the separation subroutine. We apply this result to extend the class of linear programs solvable in strongly polynomial time. We show that a problem can be solved in strongly polynomial time if, by deleting a constant number of rows and columns, it can be converted to a problem which is already known to be solvable in strongly polynomial time. For example, this yields a strongly polynomial algorithm for the concurrent multi-commodity flow problem.