### 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 language | English (US) |
---|---|

Pages (from-to) | 183-195 |

Number of pages | 13 |

Journal | Mathematical Programming, Series B |

Volume | 40 |

Issue number | 2 |

State | Published - 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

Goldfarb, D., & Mehrotra, S. (1988). RELAXED VARIANTS OF KARMARKAR'S ALGORITHM FOR LINEAR PROGRAMS WITH UNKNOWN OPTIMAL OBJECTIVE VALUE.

*Mathematical Programming, Series B*,*40*(2), 183-195.