Probabilistic bounds on one step objective/potential function improvement in Karmarkar's algorithm

M. Minoux

RAIRO - Operations Research - Recherche Opérationnelle (1994)

  • Volume: 28, Issue: 4, page 329-355
  • ISSN: 0399-0559

How to cite

top

Minoux, M.. "Probabilistic bounds on one step objective/potential function improvement in Karmarkar's algorithm." RAIRO - Operations Research - Recherche Opérationnelle 28.4 (1994): 329-355. <http://eudml.org/doc/105088>.

@article{Minoux1994,
author = {Minoux, M.},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {interior point methods; probabilistic analysis; Karmarkar's algorithm; worst case analysis},
language = {eng},
number = {4},
pages = {329-355},
publisher = {EDP-Sciences},
title = {Probabilistic bounds on one step objective/potential function improvement in Karmarkar's algorithm},
url = {http://eudml.org/doc/105088},
volume = {28},
year = {1994},
}

TY - JOUR
AU - Minoux, M.
TI - Probabilistic bounds on one step objective/potential function improvement in Karmarkar's algorithm
JO - RAIRO - Operations Research - Recherche Opérationnelle
PY - 1994
PB - EDP-Sciences
VL - 28
IS - 4
SP - 329
EP - 355
LA - eng
KW - interior point methods; probabilistic analysis; Karmarkar's algorithm; worst case analysis
UR - http://eudml.org/doc/105088
ER -

References

top
  1. 1. I. ADLER, N. KARMARKAR, M. G. C. RESENDE and G. VEIGA, An implementation of Karmarkar's algorithm for linear programming, Dept. Industrial Engineering and Operations Research, University of California, Berkeley, 1988. Zbl0682.90061
  2. 2. K. M. ANSTREICHER, The worst-case step in Karmarkar's algorithm, Mathematics of Ops. Res., 1989, 14, 2, pp. 294-302. Zbl0674.90060MR997036
  3. 3. C. Mc DIARMID, On the improvement per iteration in Karmarkar's method for linear programming, Institute of Economics and Statistics, Oxford University, England, 1986. 
  4. 4. R. B. GOLDSTEIN, Chi-square quantiles, Communications of the A. C. M., 1973, 6, n° 8, pp. 483-485. 
  5. 5. N. KARMARKAR, A new polynomial-time algorithm for linear programming, Combinatorica, 1984, 4, 4, pp. 373-395. Zbl0557.90065MR779900
  6. 6. M. MINOUX, Towards a probabilistic analysis of Karmarkar's algorithm, Colloque Franco-Soviétique de Programmation Mathématique. Marseille, Luminy 8-12 Octobre 1990. 
  7. 7. A. S. NEMIROVSKI, An algorithm of the Karmarkar type, Tekhnicheskaya Kibernetika n°1, 1987, p. 105-118, English Translation in Scripta Technica 1988. Zbl0654.90048MR929639
  8. 8. M. PADBERG, A different convergence proof of the projective method for linear programming, New York University, 1985. Zbl0617.90059MR836260
  9. 9. M. J. D. POWELL, On the number of iterations of Karmarkar's algorithm for linear programming, Mathematical Programming, 1993, 62, pp. 153-197. Zbl0804.90092MR1247612
  10. 10. J. A. TOMLIN, An experimental approach to Karmarkar's projective method for linear programming, Ketron, Inc., Mountain View, CA 94040, 1985. Zbl0634.90044
  11. 11. M. J. TODD, Anticipated behaviour of Karmarkar's algorithm, Technical Report n° 879, Cornell University, Ithaca, New York, 14853, 1989. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.