Random Walks on Polytopes and an Affine Interior Point Method for Linear Programming
Random Walks on Polytopes and an Affine Interior Point Method for Linear Programming
About this item
Full title
Random Walks on Polytopes and an Affine Interior Point Method for Linear Programming
Author / Creator
Publisher
Linthicum: INFORMS
Journal title
Mathematics of operations research, 2012-02, Vol.37 (1), p.1-20
Language
English
Formats
Publication information
Publisher
Linthicum: INFORMS
Subjects
More information
Scope and Contents
Contents
Let
K
be a polytope in
n
defined by
m
linear inequalities. We give a new Markov chain algorithm to draw a nearly uniform sample from
K
. The underlying Markov chain is the first to have a mixing time that is strongly polynomial when started from a "central" point. We use this result to design an affine interior point algorit...
Alternative Titles
Full title
Random Walks on Polytopes and an Affine Interior Point Method for Linear Programming
Authors, Artists and Contributors
Author / Creator
Identifiers
Primary Identifiers
Record Identifier
TN_cdi_econis_primary_689040865
Permalink
https://devfeature-collection.sl.nsw.gov.au/record/TN_cdi_econis_primary_689040865
Other Identifiers
ISSN
0364-765X
E-ISSN
1526-5471
DOI
10.1287/moor.1110.0519
