A primal-simplex based Tardos’ algorithm

详细信息    查看全文

• 作者：Shinji Mizuno^a ; ^{mizuno.s.ab@m.titech.ac.jp" class="auth_mail" title="E-mail the corresponding author} ; Noriyoshi Sukegawa^b ; ^{sukegawa@ise.chuo-u.ac.jp" class="auth_mail" title="E-mail the corresponding author} ; Antoine Deza^c ; ^{deza@mcmaster.ca" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Tardos&rsquo ; algorithm ; Simplex method ; Strongly polynomial algorithm ; Total unimodularity
• 刊名：Operations Research Letters
• 出版年：2015
• 出版时间：November 2015
• 年：2015
• 卷：43
• 期：6
• 页码：625-628
• 全文大小：373 K

文摘

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 in the dimension of the input. 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 the simplex method to solve the auxiliary problems. The proposed algorithm is strongly polynomial if the coefficient matrix is totally unimodular and the auxiliary problems are non-degenerate.