Karmarkar's algorithm with improved steps

Research output: Contribution to journalArticle

5 Citations (Scopus)

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 languageEnglish (US)
Pages (from-to)73-78
Number of pages6
JournalMathematical Programming
Volume46
Issue number1-3
DOIs
StatePublished - Jan 1 1990

Fingerprint

Karmarkar's Algorithm
Linear Program
Feasible region
Dependent Data
Potential Function
Supremum
Interior
If and only if
Zero
Linear program

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

@article{ada41f298d4e4200a11d5e1355b3439b,
title = "Karmarkar's algorithm with improved steps",
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.",
author = "Bahman Kalantari",
year = "1990",
month = "1",
day = "1",
doi = "10.1007/BF01585728",
language = "English (US)",
volume = "46",
pages = "73--78",
journal = "Mathematical Programming",
issn = "0025-5610",
publisher = "Springer-Verlag GmbH and Co. KG",
number = "1-3",

}

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

In: Mathematical Programming, Vol. 46, No. 1-3, 01.01.1990, p. 73-78.

Research output: Contribution to journalArticle

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 -