polynomial-time

Using Nemirovski’s Mirror-Prox method as Basic Procedure in Chubanov’s method for solving homogeneous feasibility problems

  • Cornelis Roos
  • Wei Zhang
    • Categories Applications - OR and Management Sciences, Linear Programming Tags ,

    We introduce a new variant of Chubanov’s method for solving linear homogeneous systems with positive variables. In the \BP\ we use a recently introduced cut in combination with Nemirovski’s Mirror-Prox method. We show that the cut requires at most $O(n^3)$ time, just as Chabonov’s cut. In an earlier paper it was shown that the new … Read more

    An improved version of Chubanov’s method for solving a homogeneous feasibility problem

  • Cornelis Roos
    • Categories Linear Programming Tags ,

    We deal with a recently proposed method of Chubanov [1] for solving linear homogeneous systems with positive variables. Some improvements of Chubanov’s method and its analysis are presented. We propose a new and simple cut criterion and show that the cuts defined by the new criterion are at least as sharp as in [1]. The … Read more