Optimization Online


A primal-simplex based Tardos' algorithm

Shinji Mizuno (mizuno.s.ab***at***m.titech.ac.jp)
Noriyoshi Sukegawa (sukegawa.n.aa***at***m.titech.ac.jp)
Antoine Deza (deza***at***mcmaster.ca)

Abstract: 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 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.

Keywords: Tardos' algorithm, simplex method, strongly polynomial algorithm, total unimodularity

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

Citation: Technical Report 2014-4, Department of Industrial Engineering and Management, Tokyo Institute of Technology

Download: [PDF]

Entry Submitted: 09/07/2014
Entry Accepted: 09/07/2014
Entry Last Modified: 09/07/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society