{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,22]],"date-time":"2026-01-22T06:36:17Z","timestamp":1769063777894,"version":"3.49.0"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2019,3,1]],"date-time":"2019-03-01T00:00:00Z","timestamp":1551398400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[2020,4]]},"DOI":"10.1007\/s10479-019-03186-2","type":"journal-article","created":{"date-parts":[[2019,3,1]],"date-time":"2019-03-01T11:01:19Z","timestamp":1551438079000},"page":"593-616","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["A linear programming primer: from Fourier to Karmarkar"],"prefix":"10.1007","volume":"287","author":[{"given":"Atlanta","family":"Chakraborty","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vijay","family":"Chandru","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9980-3051","authenticated-orcid":false,"given":"M. R.","family":"Rao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,3,1]]},"reference":[{"key":"3186_CR1","doi-asserted-by":"publisher","first-page":"955","DOI":"10.1287\/opre.39.6.955","volume":"39","author":"I Adler","year":"1991","unstructured":"Adler, I., & Cosares, S. (1991). A strongly polynomial algorithm for a special class of linear programs. Operations Research, 39, 955\u2013960.","journal-title":"Operations Research"},{"issue":"1","key":"3186_CR2","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1287\/ijoc.6.1.15","volume":"6","author":"RE Bixby","year":"1994","unstructured":"Bixby, R. E. (1994). Progress in linear programming. ORSA Journal on Computing, 6(1), 15\u201322.","journal-title":"ORSA Journal on Computing"},{"key":"3186_CR3","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-61578-8","volume-title":"The simplex method: A probabilistic analysis","author":"KH Borgwardt","year":"1987","unstructured":"Borgwardt, K. H. (1987). The simplex method: A probabilistic analysis. Berlin: Springer."},{"key":"3186_CR4","first-page":"1314","volume":"139","author":"RN Cerkinov","year":"1961","unstructured":"Cerkinov, R. N. (1961). The solution of linear programming problems by elimination of unknowns. Doklady Akademii Nauk, 139, 1314\u20131317.","journal-title":"Doklady Akademii Nauk"},{"key":"3186_CR5","unstructured":"Chandru, V., & Kochar, B. S. (1985). A class of algorithms for linear programming, Research Memorandum No. 85-14, Purdue University."},{"key":"3186_CR6","unstructured":"Chandru, V., & Kochar, B. S. (1986). Exploiting special structures using a variant of Karmarkar\u2019s algorithm, Research Memorandum No. 86-10, School of Industrial Engineering, Purdue University."},{"issue":"5","key":"3186_CR7","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1093\/comjnl\/36.5.463","volume":"36","author":"V Chandru","year":"1993","unstructured":"Chandru, V. (1993). Variable elimination in linear constraints. The Computer Journal, 36(5), 463\u2013472.","journal-title":"The Computer Journal"},{"key":"3186_CR8","doi-asserted-by":"publisher","first-page":"160","DOI":"10.2307\/1907845","volume":"20","author":"A Charnes","year":"1952","unstructured":"Charnes, A. (1952). Optimality and degeneracy in linear programming. Econometrica, 20, 160\u2013170.","journal-title":"Econometrica"},{"key":"3186_CR9","doi-asserted-by":"crossref","unstructured":"Cohen, E., & Megiddo, N. (1991). Improved algorithms for linear inequalities with two variables per inequality. In Proceedings of the twenty third symposium on theory of computing, New Orleans (pp. 145\u2013155).","DOI":"10.1145\/103418.103438"},{"key":"3186_CR10","unstructured":"Cohen, E., & Megiddo, N. (1993). New algorithms for generalized network flows, Revised. In D. Dolev, Z. Galil, & M. Rodeh (Eds.), Proceedings of the 1st Israeli symposium on the theory of computing and systems (pp. 103\u2013114)."},{"key":"3186_CR11","doi-asserted-by":"publisher","first-page":"1313","DOI":"10.1137\/S0097539791256325","volume":"23","author":"E Cohen","year":"1994","unstructured":"Cohen, E., & Megiddo, N. (1994). Improved algorithms for linear inequalities with two variables per inequality, Extended Abstract. SIAM Journal of Computing, 23, 1313\u20131347.","journal-title":"SIAM Journal of Computing"},{"key":"3186_CR12","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1007\/BF01584992","volume":"3","author":"RW Cottle","year":"1972","unstructured":"Cottle, R. W., & Veinott, A. F, Jr. (1972). Polyhedral sets having a least element. Mathematical Programming, 3, 238\u2013249.","journal-title":"Mathematical Programming"},{"key":"3186_CR13","first-page":"339","volume-title":"Activity analysis of production and allocation","author":"GB Dantzig","year":"1951","unstructured":"Dantzig, G. B. (1951). Maximization of a linear function of variables subject to linear inequalities. In C. Koopmans (Ed.), Activity analysis of production and allocation (pp. 339\u2013347). New York: Wiley."},{"key":"3186_CR14","doi-asserted-by":"publisher","DOI":"10.7249\/R366","volume-title":"Linear programming and extensions","author":"GB Dantzig","year":"1963","unstructured":"Dantzig, G. B. (1963). Linear programming and extensions. Princeton: Princeton University Press."},{"key":"3186_CR15","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1016\/0097-3165(73)90004-6","volume":"14","author":"GB Dantzig","year":"1973","unstructured":"Dantzig, G. B., & Eaves, B. C. (1973). Fourier\u2013Motzkin elimination and its dual. Journal of Combinatorial Theory (A), 14, 288\u2013297.","journal-title":"Journal of Combinatorial Theory (A)"},{"key":"3186_CR16","doi-asserted-by":"publisher","first-page":"183","DOI":"10.2140\/pjm.1955.5.183","volume":"5","author":"GB Dantzig","year":"1955","unstructured":"Dantzig, G. B., Orden, A., & Wolfe, P. (1955). The generalized simplex method for minimizing a linear form under linear inequality restraints. Pacific Journal of Mathematics, 5, 183\u2013195.","journal-title":"Pacific Journal of Mathematics"},{"key":"3186_CR17","unstructured":"Fourier, L. B. J. (1826). Reported in: Analyse des travaux de l\u2019Academic Royale des Sciences. pendant l\u2019annee (1823), Partie mathematique, Histoire de l\u2019Academie Royale des Sciences de l\u2019Institut de France (Vol. 6, pp. xxix\u2013xli)."},{"key":"3186_CR18","unstructured":"Fourier, L. B. J. (1827). Reported in: Analyse des travaux de l\u2019Academic Royale des Sciences. pendant l\u2019annee (1824), Partie mathematique, Histoire de l\u2019Academie Royale des Sciences de l\u2019Institut de France (Vol. 7, pp. xlviii\u2013lv) (Partial English Translation in: D.A. Kohler, Translation of a report by Fourier on his work on linear inequalities. Opsearch, Vol. 10, pp. 38\u201342, 1973)"},{"key":"3186_CR19","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/BF02579273","volume":"1","author":"M Gr\u00f6tschel","year":"1982","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., & Schrijver, A. (1982). The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1, 169\u2013197.","journal-title":"Combinatorica"},{"key":"3186_CR20","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric algorithms and combinatorial optimization","author":"M Gr\u00f6tschel","year":"1988","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., & Schrijver, A. (1988). Geometric algorithms and combinatorial optimization. Berlin: Springer."},{"key":"3186_CR21","first-page":"191","volume":"20","author":"LG Ha\u0109ijan","year":"1979","unstructured":"Ha\u0109ijan, L. G. (1979). A polynomial algorithm in linear programming. Soviet Mathematics Doklady, 20, 191\u2013194.","journal-title":"Soviet Mathematics Doklady"},{"key":"3186_CR22","unstructured":"Haimovich, M. (1983). The simplex method is very good! On the expected number of pivot steps and related properties of random linear programs. Unpublished Manuscript."},{"issue":"6","key":"3186_CR23","doi-asserted-by":"publisher","first-page":"1179","DOI":"10.1137\/S0097539793251876","volume":"23","author":"DS Hochbaum","year":"1994","unstructured":"Hochbaum, D. S., & Naor, J. (1994). Simple and Fast Algorithms for Linear and Integer Programs with two variables per inequality. SIAM Journal on Computing, 23(6), 1179\u20131192.","journal-title":"SIAM Journal on Computing"},{"key":"3186_CR24","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/BF02579150","volume":"4","author":"NK Karmarkar","year":"1984","unstructured":"Karmarkar, N. K. (1984). A new polynomial-time algorithm for linear programming. Combinatorica, 4, 373\u2013395.","journal-title":"Combinatorica"},{"key":"3186_CR25","doi-asserted-by":"publisher","first-page":"620","DOI":"10.1137\/0211053","volume":"11","author":"RM Karp","year":"1982","unstructured":"Karp, R. M., & Papadimitriou, C. H. (1982). On linear characterizations of combinatorial optimization problems. SIAM Journal on Computing, 11, 620\u2013632.","journal-title":"SIAM Journal on Computing"},{"key":"3186_CR26","volume-title":"Inequalities III","author":"V Klee","year":"1972","unstructured":"Klee, V., & Minty, G. J. (1972). How good is the simplex algorithm? In O. Shisha (Ed.), Inequalities III. Cambridge: Academic Press."},{"key":"3186_CR27","doi-asserted-by":"crossref","unstructured":"Lassez, J.-L. (1991). From LP to LP: Programming with constraints. In Proceedings of theoretical aspects of computer software, Sendai.","DOI":"10.1007\/3-540-54415-1_57"},{"key":"3186_CR28","unstructured":"Lassez, J.-L., & Maher, M. J. (1988). On Fourier\u2019s algorithm for linear arithmetic constraints, IBM Research Report, T Watson Research Center."},{"issue":"2","key":"3186_CR29","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1137\/0212022","volume":"12","author":"N Megiddo","year":"1983","unstructured":"Megiddo, N. (1983). Towards a genuinely polynomial algorithm for linear programming. SIAM Journal on Computing, 12(2), 347\u2013353.","journal-title":"SIAM Journal on Computing"},{"key":"3186_CR30","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1287\/ijoc.3.1.63","volume":"3","author":"N Megiddo","year":"1991","unstructured":"Megiddo, N. (1991). On finding primal- and dual-optimal bases. ORSA Journal on Computing, 3, 63\u201365.","journal-title":"ORSA Journal on Computing"},{"key":"3186_CR31","unstructured":"Motzkin, T. S. (1936). Beitrage zur theorie der linearen Ungleichungen. Doctoral thesis, University of Base."},{"key":"3186_CR32","volume-title":"The Russian method for linear inequalities, Part III, Bounded integer programming","author":"MW Padberg","year":"1981","unstructured":"Padberg, M. W., & Rao, M. R. (1981). The Russian method for linear inequalities, Part III, Bounded integer programming. New York: New York University. (preprint)."},{"key":"3186_CR33","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-2311-6","volume-title":"Linear programming: A modern integrated analysis","author":"R Saigal","year":"1995","unstructured":"Saigal, R. (1995). Linear programming: A modern integrated analysis. Alphen aan den Rijn: Kluwer Press."},{"key":"3186_CR34","volume-title":"Theory of linear and integer programming","author":"A Schrijver","year":"1986","unstructured":"Schrijver, A. (1986). Theory of linear and integer programming. Hoboken: Wiley."},{"key":"3186_CR35","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1007\/BF01070506","volume":"6","author":"NZ Shor","year":"1970","unstructured":"Shor, N. Z. (1970). Convergence rate of the gradient descent method with dilation of the space. Cybernetics, 6, 102\u2013108.","journal-title":"Cybernetics"},{"issue":"2","key":"3186_CR36","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1137\/1033049","volume":"33","author":"Richard E Stone","year":"1991","unstructured":"Stone, Richard E., & Tovey, Craig A. (1991). The simplex and projective scaling algorithms as iteratively reweighted least squares methods. SIAM Review, 33(2), 220\u2013237.","journal-title":"SIAM Review"},{"key":"3186_CR37","unstructured":"Todd, M. J. (1986). Exploiting special structure in Karmarkar\u2019s algorithm for linear programming. Technical Report 707, School of Operations Research and Industrial Engineering, Cornell University."},{"issue":"1","key":"3186_CR38","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1287\/ijoc.6.1.28","volume":"6","author":"MJ Todd","year":"1994","unstructured":"Todd, M. J. (1994). Theory and practice for interior-point methods. ORSA Journal on Computing, 6(1), 28\u201331.","journal-title":"ORSA Journal on Computing"},{"key":"3186_CR39","doi-asserted-by":"crossref","unstructured":"Vaidya, P. M. (1989). Speeding-up linear programming using fast matrix multiplication. In Proceedings of the 30th IEEE annual symposium on foundations of computer science (pp. 332\u2013337).","DOI":"10.1109\/SFCS.1989.63499"},{"key":"3186_CR40","volume-title":"Linear programming: Foundations and extensions","author":"RJ Vanderbei","year":"2015","unstructured":"Vanderbei, R. J. (2015). Linear programming: Foundations and extensions (4th ed.). Berlin: Springer.","edition":"4"},{"key":"3186_CR41","doi-asserted-by":"publisher","first-page":"681","DOI":"10.1080\/00029890.1986.11971923","volume":"93","author":"HP Williams","year":"1986","unstructured":"Williams, H. P. (1986). Fourier\u2019s method of linear programming and its dual. The America Mathematical Monthly, 93, 681\u2013695.","journal-title":"The America Mathematical Monthly"},{"issue":"205","key":"3186_CR42","first-page":"211","volume":"11","author":"P Wolfe","year":"1963","unstructured":"Wolfe, P. (1963). A technique for resolving degeneracy in linear programming. SIAM Journal on Applied Mathematics, 11(205), 211.","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"3186_CR43","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611971453","volume-title":"Primal-dual interior-point methods","author":"SJ Wright","year":"1997","unstructured":"Wright, S. J. (1997). Primal-dual interior-point methods. Cambridge: SIAM Press."},{"key":"3186_CR44","volume-title":"Convex polytopes","author":"M Ziegler","year":"1995","unstructured":"Ziegler, M. (1995). Convex polytopes. Berlin: Springer."}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-019-03186-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10479-019-03186-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-019-03186-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,3,13]],"date-time":"2020-03-13T00:35:46Z","timestamp":1584059746000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10479-019-03186-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3,1]]},"references-count":44,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,4]]}},"alternative-id":["3186"],"URL":"https:\/\/doi.org\/10.1007\/s10479-019-03186-2","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,3,1]]},"assertion":[{"value":"1 March 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}