AN ENHANCED PRIMAL-SIMPLEX BASED TARDOS' ALGORITHM FOR LINEAR OPTIMIZATION

Access this Article

Search this Article

Author(s)

Abstract

<p>While the algorithmic complexity is in general worse than the one of Tardos' original algorithms, the authors, motivated by the practicality of such methods, recently proposed a simplex-based variant that is strongly polynomial if the coefficient matrix is totally unimodular and the auxiliary problems are non-degenerate. In this paper, we introduce a slight modification that circumvents the determination of the largest sub-determinant while keeping the same theoretical performance. Assuming that the coefficient matrix is integer-valued and the auxiliary problems are non-degenerate, the proposed algorithm is polynomial in the dimension of the input data and the largest absolute value of a sub-determinant of the coefficient matrix.</p>

Journal

  • Journal of the Operations Research Society of Japan

    Journal of the Operations Research Society of Japan 61(2), 186-196, 2018

    The Operations Research Society of Japan

Codes

  • NII Article ID (NAID)
    130006602084
  • NII NACSIS-CAT ID (NCID)
    AA00703935
  • Text Lang
    ENG
  • ISSN
    0453-4514
  • NDL Article ID
    028921180
  • NDL Call No.
    Z53-M226
  • Data Source
    NDL  J-STAGE 
Page Top