A dual version of Tardos's algorithm for linear programming (Q581226): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 01:42, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A dual version of Tardos's algorithm for linear programming |
scientific article |
Statements
A dual version of Tardos's algorithm for linear programming (English)
0 references
1986
0 references
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.
0 references
polynomial complexities
0 references
dual program
0 references