A dual version of Tardos's algorithm for linear programming (Q581226): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
| Property / cites work | |||
| Property / cites work: A capacity-rounding algorithm for the minimum-cost circulation problem: A dual framework of the Tardos algorithm / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: A new polynomial-time algorithm for linear programming / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: A strongly polynomial minimum cost circulation algorithm / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs / rank | |||
Normal rank | |||
Latest revision as of 12:30, 18 June 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
0 references
