A dual version of Tardos's algorithm for linear programming (Q581226)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4018766
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | A dual version of Tardos's algorithm for linear programming |
scientific article; zbMATH DE number 4018766 |
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
0 references
0.8213081955909729
0 references
0.7758558392524719
0 references
0.7750110626220703
0 references
