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
      0 references
      0 references
      1987
      0 references
      Karmarkar's algorithm
      0 references
      duality
      0 references
      cutting objective
      0 references
      polynomial-time complexity
      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

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references