### Abstract

We define a function of the interior of the feasible region of Karmarkar's canonical linear program with the property that its supremum is bounded above by one, if and only if the optimal value of the linear program is zero. We use this function to obtain data-dependent steps for Karmarkar's algorithm. The corresponding reduction in the potential function improves upon the data-independent reduction derived by Padberg. We analyze the general step and consider its potential practical advantages.

Original language | English (US) |
---|---|

Pages (from-to) | 73-78 |

Number of pages | 6 |

Journal | Mathematical Programming |

Volume | 46 |

Issue number | 1-3 |

DOIs | |

State | Published - Jan 1 1990 |

### Fingerprint

### All Science Journal Classification (ASJC) codes

- Applied Mathematics
- Mathematics(all)
- Safety, Risk, Reliability and Quality
- Management Science and Operations Research
- Software
- Computer Graphics and Computer-Aided Design
- Computer Science(all)

### Cite this

*Mathematical Programming*,

*46*(1-3), 73-78. https://doi.org/10.1007/BF01585728

}

*Mathematical Programming*, vol. 46, no. 1-3, pp. 73-78. https://doi.org/10.1007/BF01585728

**Karmarkar's algorithm with improved steps.** / Kalantari, Bahman.

Research output: Contribution to journal › Article

TY - JOUR

T1 - Karmarkar's algorithm with improved steps

AU - Kalantari, Bahman

PY - 1990/1/1

Y1 - 1990/1/1

N2 - We define a function of the interior of the feasible region of Karmarkar's canonical linear program with the property that its supremum is bounded above by one, if and only if the optimal value of the linear program is zero. We use this function to obtain data-dependent steps for Karmarkar's algorithm. The corresponding reduction in the potential function improves upon the data-independent reduction derived by Padberg. We analyze the general step and consider its potential practical advantages.

AB - We define a function of the interior of the feasible region of Karmarkar's canonical linear program with the property that its supremum is bounded above by one, if and only if the optimal value of the linear program is zero. We use this function to obtain data-dependent steps for Karmarkar's algorithm. The corresponding reduction in the potential function improves upon the data-independent reduction derived by Padberg. We analyze the general step and consider its potential practical advantages.

UR - http://www.scopus.com/inward/record.url?scp=0025252669&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0025252669&partnerID=8YFLogxK

U2 - 10.1007/BF01585728

DO - 10.1007/BF01585728

M3 - Article

VL - 46

SP - 73

EP - 78

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

IS - 1-3

ER -