Recovering optimal dual solutions in Karmarkar's polynomial algorithm for linear programming (Q3780756)
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 4043608
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Recovering optimal dual solutions in Karmarkar's polynomial algorithm for linear programming |
scientific article; zbMATH DE number 4043608 |
Statements
Recovering optimal dual solutions in Karmarkar's polynomial algorithm for linear programming (English)
0 references
1987
0 references
Karmarkar's algorithm
0 references
duality
0 references
cutting objective
0 references
polynomial-time complexity
0 references
0 references
0 references
0.8921710848808289
0 references
0.8557410836219788
0 references
0.8524084091186523
0 references
0.8407543301582336
0 references
0.8333969712257385
0 references
This paper presents a ``standard form'' variant of Karmarkar's algorithm for linear programming. The techniques of using duality and cutting objective are combined in this variant to maintain polynomial-time complexity and to bypass the difficulties found in Karmarkar's original algorithm. The variant works with problems in standard form and simultaneously generates sequences of primal and dual feasible solutions whose objective function values converge to the unknown optimal value. Some computational results are also reported.
0 references