{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,1,25]],"date-time":"2024-01-25T13:42:32Z","timestamp":1706190152706},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"1-4","license":[{"start":{"date-parts":[[1986,11,1]],"date-time":"1986-11-01T00:00:00Z","timestamp":531187200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1986,11]]},"DOI":"10.1007\/bf01840453","type":"journal-article","created":{"date-parts":[[2005,7,13]],"date-time":"2005-07-13T21:29:13Z","timestamp":1121290153000},"page":"387-394","source":"Crossref","is-referenced-by-count":30,"title":["Introduction: New approaches to linear programming"],"prefix":"10.1007","volume":"1","author":[{"given":"Nimrod","family":"Megiddo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF01840453_CR1","doi-asserted-by":"crossref","first-page":"483","DOI":"10.1007\/BF01840458","volume":"1","author":"K. M. Anstreicher","year":"1986","unstructured":"K. M. Anstreicher, A monotonic projective algorithm for fractional linear programming,Algorithmica,1 (1986), 483\u2013498.","journal-title":"Algorithmica"},{"key":"BF01840453_CR2","doi-asserted-by":"crossref","unstructured":"K. M. Anstreicher, A strengthened acceptance criterion for approximate projections in Karmarkar's algorithm, Report, Yale School of Organization and Management, 1986.","DOI":"10.1016\/0167-6377(86)90080-5"},{"key":"BF01840453_CR3","series-title":"Report ORC","volume-title":"An implementation of Karmarkar's algorithm for linear programming","author":"I. Adler","year":"1986","unstructured":"I. Adler, M. G. C. Resende, and G. Veiga, An implementation of Karmarkar's algorithm for linear programming, Report ORC 86-8, Operations Research Center, University of California, Berkeley, CA, 1986."},{"key":"BF01840453_CR4","series-title":"Research Report No.","volume-title":"A variation on Karmarkar's algorithm for solving linear programming problems","author":"E. R. Barnes","year":"1985","unstructured":"E. R. Barnes, A variation on Karmarkar's algorithm for solving linear programming problems, Research Report No. RC 11136, IBM T. S. Watson Research Center, Yorktown Heights, NY, 1985."},{"key":"BF01840453_CR5","unstructured":"D. A. Bayer and J. C. Lagarias, The nonlinear geometry of linear programming, I: affine and projective rescaling trajectories, AT&T preprint, 1986."},{"key":"BF01840453_CR6","unstructured":"U. Betke and P. Gritzmann, Projection algorithms for linear programming, presented at the 1986 AMS-IMS-SIAM Summer Research Conference on Discrete and Computational Geoemtry, Santa Cruz, CA, 1986."},{"key":"BF01840453_CR7","doi-asserted-by":"crossref","first-page":"537","DOI":"10.1007\/BF01840462","volume":"1","author":"C. E. Blair","year":"1986","unstructured":"C. E. Blair, The iterative step in the linear programming algorithm of N. Karmarkar,Algorithmica,1 (1986), 537\u2013539.","journal-title":"Algorithmica"},{"key":"BF01840453_CR8","unstructured":"L. G. Blum, Towards an asymptotic analysis of Karmarkar's algorithm, Extended Abstract, 1985."},{"key":"BF01840453_CR9","unstructured":"T. M. Cavalier and A. L. Soyster, Some computational experience and a modification of the Karmarkar algorithm, presented at the 12th Symposium on Mathematical Programming, Cambridge, MA, 1985."},{"key":"BF01840453_CR10","unstructured":"V. Chandru and B. P. Kochar, A class of algorithms for linear programming, presented at the 12th Symposium on Mathematical Programming, Cambridge, MA, 1985."},{"key":"BF01840453_CR11","unstructured":"A. Charnes, T. Song, and M. Wolfe, An explicit solution sequence and convergence of Karmarkar's algorithm, manuscript, University of Texas at Austin, 1984."},{"key":"BF01840453_CR12","unstructured":"S. Chen, Computational experience with the Karmarkar algorithm, presented at the Joint National TIMS\/ORSA Meeting, Los Angeles, CA, 1986."},{"key":"BF01840453_CR13","unstructured":"G. de Ghellinck and J.-Ph. Vial, An extension of Karmarkar's algorithm for solving a system of linear homogenous equations on the simplex, Discussion Paper No. 8538, C.O.R.E., Catholic University of Louvain, 1985."},{"key":"BF01840453_CR14","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1007\/BF01840456","volume":"1","author":"G. Ghellinck de","year":"1986","unstructured":"G. de Ghellinck and J.-Ph. Vial, A polynomial Newton method for linear programming,Algorithmica,1 (1986), 425\u2013453.","journal-title":"Algorithmica"},{"key":"BF01840453_CR15","volume-title":"The logarithmic potential method of convex programming","author":"K. R. Frisch","year":"1955","unstructured":"K. R. Frisch, The logarithmic potential method of convex programming, unpublished manuscript, University Institute of Economics, Oslo, 1955."},{"key":"BF01840453_CR16","series-title":"Report","volume-title":"A variant of Karmarkar's linear programming algorithm for problems in standard form","author":"D. M. Gay","year":"1985","unstructured":"D. M. Gay, A variant of Karmarkar's linear programming algorithm for problems in standard form, Report, AT&T Bell Laboratories, Murray Hill, NJ, 1985."},{"key":"BF01840453_CR17","series-title":"Technical Report SOL 85-11","doi-asserted-by":"crossref","DOI":"10.21236\/ADA158212","volume-title":"On projected Newton barrier methods for linear programming and an equivalence to Karmarkar's projective method","author":"P. E. Gill","year":"1985","unstructured":"P. E. Gill, W. Murray, M. A. Saunders, J. A. Tomlin, and M. H. Wright, On projected Newton barrier methods for linear programming and an equivalence to Karmarkar's projective method, Technical Report SOL 85-11, Systems Optimization Laboratory, Department of Operations Research, Stanford University, Stanford, CA, 1985."},{"key":"BF01840453_CR18","series-title":"Technical Report","volume-title":"A relaxed version of Karmarkar's method","author":"D. Goldfarb","year":"1986","unstructured":"D. Goldfarb and S. Mehrotra, A relaxed version of Karmarkar's method, Technical Report, Department of Industrial Engineering and Operations Research, Columbia University, New York, 1986."},{"key":"BF01840453_CR19","volume-title":"A conical projection algorithm for linear programming","author":"C. Gonzaga","year":"1985","unstructured":"C. Gonzaga, A conical projection algorithm for linear programming, Report Department of Electrical Engineering and Computer Science, University of California, Berkeley, CA, 1985."},{"key":"BF01840453_CR20","first-page":"207","volume-title":"Nonlinear Programming","author":"P. Huard","year":"1967","unstructured":"P. Huard, Resolution of mathematical programming with nonlinear constraints by the method of centers, inNonlinear Programming (J. Abadie, ed.), North-Holland, Amsterdam, 1967, pp. 207\u2013219."},{"key":"BF01840453_CR21","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1007\/BF01840457","volume":"1","author":"M. Iri","year":"1986","unstructured":"M. Iri and H. Imai, A multiplicative barrier function method for linear programming,Algorithmica,1 (1986), 455\u2013482.","journal-title":"Algorithmica"},{"key":"BF01840453_CR22","first-page":"147","volume-title":"Proceedings of the 18th Annual ACM Symposium on Theory of Computing","author":"S. Kapoor","year":"1986","unstructured":"S. Kapoor and P. M. Vaidya, Fast algorithms for convex quadratic programming and multicommodity flows,Proceedings of the 18th Annual ACM Symposium on Theory of Computing, ACM, New York, 1986, pp. 147\u2013159."},{"key":"BF01840453_CR23","first-page":"302","volume-title":"Proceedings of the 16th Annual ACM Symposium on Theory of Computing","author":"N. Karmarkar","year":"1984","unstructured":"N. Karmarkar, A new polynomial-time algorithm for linear programming,Proceedings of the 16th Annual ACM Symposium on Theory of Computing, ACM, New York, 1984, pp. 302\u2013311; revised version:Combinatorica,4 (1984), 373\u2013395."},{"key":"BF01840453_CR24","doi-asserted-by":"crossref","unstructured":"N. K. Karmarkar, Further developments in the new polynomial time algorithm for linear programming, presented at the 12th Symposium on Mathematical Programming, Cambridge, MA, 1985.","DOI":"10.1145\/800057.808695"},{"key":"BF01840453_CR25","unstructured":"N. K. Karmarkar and L. P. Sinha, Application of Karmarkar's algorithm to overseas telecommunications facilities planning, presented at the 12th Symposium on Mathematical Programming, Cambridge, MA, 1985."},{"key":"BF01840453_CR26","first-page":"191","volume":"20","author":"L. G. Khachiyan","year":"1979","unstructured":"L. G. Khachiyan, A polynomial algorithm in linear programming,Soviet Math. Dokl,20 (1979), 191\u2013194.","journal-title":"Soviet Math. Dokl"},{"key":"BF01840453_CR27","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1007\/BF01840459","volume":"1","author":"M. Kojima","year":"1986","unstructured":"M. Kojima, Determining basic variables of optimum solutions in Karmarkar's new LP algorithm,Algorithmica,1 (1986), 499\u2013515.","journal-title":"Algorithmica"},{"key":"BF01840453_CR28","series-title":"Research Report No.","volume-title":"An efficient implementation of Karmarkar's new LP algorithm","author":"M. Kojima","year":"1986","unstructured":"M. Kojima and K. Tone, An efficient implementation of Karmarkar's new LP algorithm, Research Report No. B-180, Department of Information Sciences, Tokyo Institute of Technology, Tokyo, 1986."},{"key":"BF01840453_CR29","unstructured":"K. O. Kortanek, D. N. Lee, and M. Shi, An application of a hybrid algorithm for semi-infinite programming, presented at the 12th Symposium on Mathematical Programming, Cambridge, MA, 1985."},{"key":"BF01840453_CR30","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1007\/BFb0121017","volume":"22","author":"O. Mangasarian","year":"1984","unstructured":"O. Mangasarian, Normal solutions of linear programs,Math. Programming Stud.,22 (1984), 206\u2013216.","journal-title":"Math. Programming Stud."},{"key":"BF01840453_CR31","unstructured":"N. Megiddo, A variation on Karmarkar's algorithm, unpublished manuscript, 1984."},{"key":"BF01840453_CR32","unstructured":"N. Megiddo, On the complexity of linear programming, inAdvances in Economic Theory (T. Bewley, ed.), Cambridge University Press, Cambridge (to appear)."},{"key":"BF01840453_CR33","unstructured":"N. Megiddo, Pathways to the set of optimal solutions in linear programming, IBM Research Report RJ5295, Almaden Research Center, 1986."},{"key":"BF01840453_CR34","unstructured":"N. Megiddo and M. Shub, Boundary behavior of interior point algorithms for linear programming, IBM Research Report RJ5319, 1986."},{"key":"BF01840453_CR35","unstructured":"G. Mitra, M. Tamiz, J. Yadegar, and K. Darby-Dowman, Experimental investigation of an interior search algorithm for linear programming, presented at the 12th Symposium on Mathematical Programming, Cambridge, MA, 1985."},{"key":"BF01840453_CR36","series-title":"Technical Paper","volume-title":"A new interior variant of the gradient projection method for linear programming","author":"K. G. Murty","year":"1985","unstructured":"K. G. Murty, A new interior variant of the gradient projection method for linear programming, Technical Paper 85-18, Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, MI, 1985."},{"key":"BF01840453_CR37","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/0167-6377(84)90003-8","volume":"3","author":"K. G. Murty","year":"1984","unstructured":"K. G. Murty and Y. Fathi, A feasible direction method for linear programming,Oper. Res. Lett.,3 (1984), 121\u2013127.","journal-title":"Oper. Res. Lett."},{"key":"BF01840453_CR38","doi-asserted-by":"crossref","first-page":"529","DOI":"10.1007\/BF01840461","volume":"1","author":"J. L. Nazareth","year":"1986","unstructured":"J. L. Nazareth, Homotopy techniques in linear programming,Algorithmica,1 (1986), 529\u2013535.","journal-title":"Algorithmica"},{"key":"BF01840453_CR39","unstructured":"M. W. Padberg, A different convergence proof of the projective method for linear programming, Report, New York University, 1985."},{"key":"BF01840453_CR40","unstructured":"M. W. Padberg, Solution of a nonlinear programming problem arising in the projective method for linear programming, Report, New York University, 1985."},{"key":"BF01840453_CR41","unstructured":"P. F. Pickel, Implementing the Karmarkar algorithm using simplex techniques, presented at the 12th Symposium on Mathematical Programming, Cambridge, MA, 1985."},{"key":"BF01840453_CR42","series-title":"I, Theory, Report","volume-title":"Approximate projections for the Karmarkar algorithm","author":"P. F. Pickel","year":"1985","unstructured":"P. F. Pickel, Approximate projections for the Karmarkar algorithm, I, Theory, Report, Polytechnic Institute of New York, Farmingdale, NY, 1985."},{"key":"BF01840453_CR43","series-title":"Report MSRI","volume-title":"A polynomial-time algorithm, based on Newton's method, for linear programming","author":"J. Renegar","year":"1986","unstructured":"J. Renegar, A polynomial-time algorithm, based on Newton's method, for linear programming, Report MSRI 07118-86, Mathematical Sciences Research Institute, Berkeley, CA, 1986."},{"key":"BF01840453_CR44","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1007\/BF01840460","volume":"1","author":"G. Rinaldi","year":"1986","unstructured":"G. Rinaldi, A projective method for linear programming with box-type constraints,Algorithmica,1 (1986), 517\u2013527.","journal-title":"Algorithmica"},{"key":"BF01840453_CR45","series-title":"Working Paper","volume-title":"On implementing Karmarkar's algorithm","author":"D. F. Shanno","year":"1985","unstructured":"D. F. Shanno and R. E. Marsten, On implementing Karmarkar's algorithm, Working Paper, Graduate School of Administration, University of California, Davis, CA, 1985."},{"key":"BF01840453_CR46","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1007\/BF01840455","volume":"1","author":"M. J. Todd","year":"1986","unstructured":"M. J. Todd and B. P. Burrell, An extension of Karmarkar's algorithm for linear programming using dual variables,Algorithmica,1 (1986), 409\u2013424.","journal-title":"Algorithmica"},{"key":"BF01840453_CR47","unstructured":"J. A. Tomlin, An experimental approach to Karmarkar's projective method for linear programming, Report, Ketron, Inc., Mountain View, CA 94040, 1985."},{"key":"BF01840453_CR48","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1007\/BF01840454","volume":"1","author":"R. J. Vanderbei","year":"1986","unstructured":"R. J. Vanderbei, M. S. Meketon, and B. A. Freedman, A modification of Karmarkar's linear programming algorithm,Algorithmica,1 (1986), 395\u2013407.","journal-title":"Algorithmica"},{"key":"BF01840453_CR49","unstructured":"Y. Ye,K-Projection and the cutting-objective methods for linear programming, presented at the 12th Symposium on Mathematical Programming, Cambridge, MA, 1985."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01840453.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01840453\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01840453","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T06:59:21Z","timestamp":1586329161000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01840453"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986,11]]},"references-count":49,"journal-issue":{"issue":"1-4","published-print":{"date-parts":[[1986,11]]}},"alternative-id":["BF01840453"],"URL":"https:\/\/doi.org\/10.1007\/bf01840453","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1986,11]]}}}