### 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

- Software
- Mathematics(all)

### Keywords

- Karmarkar's algorithm
- Linear programming

### 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, B.

Research output: Contribution to journal › Article

TY - JOUR

T1 - Karmarkar's algorithm with improved steps

AU - Kalantari, B.

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.

KW - Karmarkar's algorithm

KW - Linear programming

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

AN - SCOPUS:0025252669

VL - 46

SP - 73

EP - 78

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

IS - 1-3

ER -