A modification of karmarkar's linear programming algorithm

Robert J. Vanderbei; Marc S. Meketon; Barry A. Freedman

doi:10.1007/BF01840454

A modification of karmarkar's linear programming algorithm

Robert J. Vanderbei, Marc S. Meketon, Barry A. Freedman

Research output: Contribution to journal › Article › peer-review

128 Scopus citations

Abstract

We present a modification of Karmarkar's linear programming algorithm. Our algorithm uses a recentered projected gradient approach thereby obviating a priori knowledge of the optimal objective function value. Assuming primal and dual nondegeneracy, we prove that our algorithm converges. We present computational comparisons between our algorithm and the revised simplex method. For small, dense constraint matrices we saw little difference between the two methods.

Original language	English (US)
Pages (from-to)	395-407
Number of pages	13
Journal	Algorithmica
Volume	1
Issue number	1-4
DOIs	https://doi.org/10.1007/BF01840454
State	Published - Nov 1 1986
Externally published	Yes

All Science Journal Classification (ASJC) codes

Computer Science(all)
Computer Science Applications
Applied Mathematics

Access to Document

10.1007/BF01840454

Cite this

@article{45e8d06ae540406e87e9039ef0e2772a,

title = "A modification of karmarkar's linear programming algorithm",

abstract = "We present a modification of Karmarkar's linear programming algorithm. Our algorithm uses a recentered projected gradient approach thereby obviating a priori knowledge of the optimal objective function value. Assuming primal and dual nondegeneracy, we prove that our algorithm converges. We present computational comparisons between our algorithm and the revised simplex method. For small, dense constraint matrices we saw little difference between the two methods.",

author = "Vanderbei, {Robert J.} and Meketon, {Marc S.} and Freedman, {Barry A.}",

year = "1986",

month = nov,

day = "1",

doi = "10.1007/BF01840454",

language = "English (US)",

volume = "1",

pages = "395--407",

journal = "Algorithmica",

issn = "0178-4617",

publisher = "Springer New York",

number = "1-4",

}

TY - JOUR

T1 - A modification of karmarkar's linear programming algorithm

AU - Vanderbei, Robert J.

AU - Meketon, Marc S.

AU - Freedman, Barry A.

PY - 1986/11/1

Y1 - 1986/11/1

N2 - We present a modification of Karmarkar's linear programming algorithm. Our algorithm uses a recentered projected gradient approach thereby obviating a priori knowledge of the optimal objective function value. Assuming primal and dual nondegeneracy, we prove that our algorithm converges. We present computational comparisons between our algorithm and the revised simplex method. For small, dense constraint matrices we saw little difference between the two methods.

AB - We present a modification of Karmarkar's linear programming algorithm. Our algorithm uses a recentered projected gradient approach thereby obviating a priori knowledge of the optimal objective function value. Assuming primal and dual nondegeneracy, we prove that our algorithm converges. We present computational comparisons between our algorithm and the revised simplex method. For small, dense constraint matrices we saw little difference between the two methods.

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

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

U2 - 10.1007/BF01840454

DO - 10.1007/BF01840454

M3 - Article

AN - SCOPUS:33746951751

SN - 0178-4617

VL - 1

SP - 395

EP - 407

JO - Algorithmica

JF - Algorithmica

IS - 1-4

ER -

A modification of karmarkar's linear programming algorithm

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this