On interior algorithms for linear programming with no regularity assumptions

The linear programming algorithm of Karmarkar, and all interior methods subsequently devised, require a regularity assumption that the primal and/or dual problem possess a nonempty interior. In this note a polynomial-time interior algorithm is devised, which will directly ‘process’ and linear program, with no regularity assumptions whatsoever, without the addition of any ‘M’ terms. The present method is based on the application of a combined phase I-phase II algorithm to a combined primal-dual problem.