RELAXED VARIANTS OF KARMARKAR'S ALGORITHM FOR LINEAR PROGRAMS WITH UNKNOWN OPTIMAL OBJECTIVE VALUE.

Donald Goldfarb*, Sanjay Mehrotra

*Corresponding author for this work

Research output: Contribution to journalArticle

Abstract

Variants of Karmarkar's algorithm are given for solving linear programs with unknown optimal objective value z*. These new methods combine the approach of D. Goldfarb and S. Mehrotra for relaxing the requirement that certain projects be computed exactly with the approach of M. J. Todd and B. P. Burrell for generating an improving sequence of lower bounds for z* using dual feasible solutions. These methods retain the polynomial-time complexity of Karmarkar's algorithm.

Original languageEnglish (US)
Pages (from-to)183-195
Number of pages13
JournalMathematical Programming, Series B
Volume40
Issue number2
StatePublished - Feb 1 1988

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'RELAXED VARIANTS OF KARMARKAR'S ALGORITHM FOR LINEAR PROGRAMS WITH UNKNOWN OPTIMAL OBJECTIVE VALUE.'. Together they form a unique fingerprint.

  • Cite this