strongly polynomial algorithm

A polynomial algorithm for linear optimization which is strongly polynomial under certain conditions on optimal solutions

  • Sergei Chubanov
    • Categories Linear Programming Tags , ,

    This paper proposes a polynomial algorithm for linear programming which is strongly polynomial for linear optimization problems $\min\{c^Tx : Ax = b, x\ge {\bf 0}\}$ having optimal solutions where each non-zero component $x_j$ belongs to an interval of the form $[\alpha_j, \alpha_j\cdot 2^{p(n)}],$ where $\alpha_j$ is some positive value and $p(n)$ is a polynomial of … Read more

    A primal-simplex based Tardos’ algorithm

  • Antoine Deza
  • Shinji Mizuno
  • Noriyoshi Sukegawa
    • Categories Linear Programming Tags , , ,

    In the mid-eighties Tardos proposed a strongly polynomial algorithm for solving linear programming problems for which the size of the coefficient matrix is polynomially bounded by the dimension. Combining Orlin’s primal-based modification and Mizuno’s use of the simplex method, we introduce a modification of Tardos’ algorithm considering only the primal problem and using simplex method … Read more

    A strongly polynomial algorithm for linear optimization problems having 0-1 optimal solutions

  • Sergei Chubanov
    • Categories Linear Programming Tags ,

    We present a strongly polynomial algorithm for linear optimization problems of the form min{cx|Ax = b, x >= 0} having 0-1 vectors among their optimal solutions. The algorithm runs in time O(n^4*max\{m,log n}), where n is the number of variables and m is the number of equations. The algorithm also constructs necessary and sufficient optimality … Read more