Effects of ordering and updating techniques on the performance of the Karmarkar algorithm

Abdellah Salhi; George R. Lindfield

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

  • Volume: 25, Issue: 2, page 209-235
  • ISSN: 0399-0559

How to cite

top

Salhi, Abdellah, and Lindfield, George R.. "Effects of ordering and updating techniques on the performance of the Karmarkar algorithm." RAIRO - Operations Research - Recherche Opérationnelle 25.2 (1991): 209-235. <http://eudml.org/doc/105011>.

@article{Salhi1991,
author = {Salhi, Abdellah, Lindfield, George R.},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {Karmarkar algorithm; sparsity preservation techniques; nested dissection ordering algorithm; updating algorithm for least squares},
language = {eng},
number = {2},
pages = {209-235},
publisher = {EDP-Sciences},
title = {Effects of ordering and updating techniques on the performance of the Karmarkar algorithm},
url = {http://eudml.org/doc/105011},
volume = {25},
year = {1991},
}

TY - JOUR
AU - Salhi, Abdellah
AU - Lindfield, George R.
TI - Effects of ordering and updating techniques on the performance of the Karmarkar algorithm
JO - RAIRO - Operations Research - Recherche Opérationnelle
PY - 1991
PB - EDP-Sciences
VL - 25
IS - 2
SP - 209
EP - 235
LA - eng
KW - Karmarkar algorithm; sparsity preservation techniques; nested dissection ordering algorithm; updating algorithm for least squares
UR - http://eudml.org/doc/105011
ER -

References

top
  1. D. Avis and V. CHVÂTAL, 1978, Notes on Bland's Pivoting Rule, Math. Programming, 83 pp. 24-34. Zbl0403.65025
  2. A. BEN-ISRAEL and T. N. E. GREVILLE, Generalized Inverses, J. Wïlley and Sons, 1974 Zbl0305.15001MR396607
  3. A. CHARNES, T. SONG and M. WOLFE, An explicite Solution Sequence and Convergence of Karmarkar's Algorithm, Research Report CCS 501, Center for Cybernetic Studies, College of Business Administration 5.202, the University of Texas at Austin, Texas 78712-1177, U.S.A., 1984. 
  4. V. CHVÂTAL, Linear Programming, W. H. Freeman & Co, U.S.A., 1983. Zbl0537.90067MR717219
  5. A. GEORGE and J. W. LIU, Computer Solution of Large Sparse Positive Definite Systems, Prentice-Hall, Inc., Englewood Cliffs, NJ 07632, 1981. Zbl0516.65010MR646786
  6. M. T. HEATH, Numerical Methods for Large Sparse Linear Least Squares Problems, S.I.A.M. J. Sci. Stat. Comp., 1984, 4, (3), pp. 497-513. Zbl0575.65030MR754482
  7. J. K. Ho and E. LOUTE, A set of Staircase Linear Programming Test Problems, Math. Programming, 1980, 20, pp. 245-250. Zbl0448.90036MR607410
  8. M. HIRI and H. IMAI, A Multiplicativ Barrier Function Method for Linear Programming, Algoritkmica, 1986, 1, pp. 455-482. Zbl0641.90048MR880733
  9. N. KARMARKAR, A New Polynomial-Time Algorithm for Linear Programming, Proceedings of the 16th Annual ACM Symposium on Theory of Computing, 1984 a, pp. 302-311, Washington D.C. Zbl0557.90065MR779900
  10. N. KARMARKAR, A New Polynomial-Time Algorithm for Linear Programming, Combinatorica, 1984 b, A New Polynomial-Time Algorithm for Linear Programming, Combinatorica, 4, (4), pp.373-395. Zbl0557.90065MR779900
  11. V. KEEL and G. J. MINTY, How Good Is the Simplex Algorithm?, in Inequalities III, O. SHISHA ed., Academic Press, N. Y., 1972, pp. 159-179. Zbl0297.90047MR332165
  12. G. R. LINDFIELD and A. SALHI, A Comparative Study of the Performance and Implementation of the Karmarkar Algorithm, presented at the Martin Beale Memorial Symposium, 6-8July, 1987, The Royal Society, London. 
  13. I. J. LUSTING, A Practical Approach to Karmarkar's Algorithm, TR SOL 85-5, Department of Operations Research, Stanford University, Stanford, CA 94305, 1985. 
  14. L. E. SCHRAGE, User's Manual for LINDO, University of Chicago, U.S.A., 1983. 
  15. M. J. TODD and B. P. BURRELL, An Extension of Karmarkar's Algorithm for Linear Programming Using Dual Variables, Algorithmica, 1986, 1, pp.409-424. Zbl0621.90048MR880731
  16. J. A. TOMLIN, An Experimental Approach to Karmarkar's Projective Methods for Linear Programming, Proceedings of Symposium on Karmarkar's and Related Algorithms for Linear Programming, organized by IMA, held on May the 7th 1985 at the Geological Society, Burlington House, Piccadilly, London, 1985. Zbl0634.90044
  17. Y. YE and M. KOJIMA, Recovering Optimal Dual Solutions in Karmarkar's Algorithm for Linear Programming, Math. Programming, 39, (3), pp.305-317. Zbl0639.90062MR918872

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.