A dual version of Tardos's algorithm for linear programming

DOI10.1016/0167-6377(86)90011-8MaRDI QIDQ581226zbMATH OpenOpenAlexWikidataFDO

Authors James B. Orlin

Publication date 1986

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/1721.1/2115

zbMATH Keywords

dual programpolynomial complexities

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05)

Review text

The author considers a linear programming problem of the form min(cx: \(Ax=b\), \(x\geq 0)\) with integer coefficients. Similar to Tardos' approach which solves the dual program in time polynomial in the size of A, the author develops an algorithm which solves the primal program in time polynomial in the size of A. Some significant differences between the two methods are also discussed.

Recommendations

• A primal-simplex based Tardos' algorithm
• scientific article; zbMATH DE number 6938247
• Linear Programming in O([n3/ln n]L) Operations
• A new polynomial-time algorithm for linear programming
• scientific article; zbMATH DE number 4164543

Cites work

• A capacity-rounding algorithm for the minimum-cost circulation problem: A dual framework of the Tardos algorithm
• A new polynomial-time algorithm for linear programming
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• A strongly polynomial minimum cost circulation algorithm

Cited in

(12)

• A sequential dual simplex algorithm for the linear assignment problem
• On max-flow min-cut and integral flow properties for multicommodity flows in directed networks
• A primal-simplex based Tardos' algorithm
• A variant of the dual face algorithm using Gauss-Jordan elimination for linear programming
• Mobile facility location: combinatorial filtering via weighted occupancy
• scientific article; zbMATH DE number 5013903 (Why is no real title available?)
• Scarf's Procedure for Integer Programming and a Dual Simplex Algorithm
• A Variant of the Dual Pivoting Rule in Linear Programming
• A Dual Simplex Algorithm for Piecewise-Linear Programming
• scientific article; zbMATH DE number 851571 (Why is no real title available?)
• scientific article; zbMATH DE number 6938247 (Why is no real title available?)
• Multicommodity flows in certain planar directed networks

This page was built for publication: A dual version of Tardos's algorithm for linear programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q581226)