{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,16]],"date-time":"2025-12-16T12:07:33Z","timestamp":1765886853935},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"1-3","license":[{"start":{"date-parts":[[1992,8,1]],"date-time":"1992-08-01T00:00:00Z","timestamp":712627200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Programming"],"published-print":{"date-parts":[[1992,8]]},"DOI":"10.1007\/bf01580902","type":"journal-article","created":{"date-parts":[[2005,4,28]],"date-time":"2005-04-28T08:58:11Z","timestamp":1114678691000},"page":"245-284","source":"Crossref","is-referenced-by-count":58,"title":["Solving combinatorial optimization problems using Karmarkar's algorithm"],"prefix":"10.1007","volume":"56","author":[{"given":"John E.","family":"Mitchell","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael J.","family":"Todd","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1007\/BF01587095","volume":"44","author":"I. Adler","year":"1989","unstructured":"I. Adler, M.G.C. Resende, G. Veiga and N.K. Karmarkar, \u201cAn implementation of Karmarkar's algorithm for linear programming,\u201dMathematical Programming 44 (1989) 297\u2013335.","journal-title":"Mathematical Programming"},{"key":"CR2","doi-asserted-by":"crossref","first-page":"483","DOI":"10.1007\/BF01840458","volume":"1","author":"K.M. Anstreicher","year":"1986","unstructured":"K.M. Anstreicher, \u201cA monotonic projection algorithm for fractional linear programming,\u201dAlgorithmica 1 (1986) 483\u2013498.","journal-title":"Algorithmica"},{"key":"CR3","first-page":"499","volume":"314","author":"D.A. Bayer","year":"1989","unstructured":"D.A. Bayer and J.C. Lagarias, \u201cThe nonlinear geometry of linear programming I. Affine and projective scaling trajectories,\u201dTransactions of the American Mathematical Society 314 (1989) 499\u2013526.","journal-title":"Transactions of the American Mathematical Society"},{"key":"CR4","first-page":"527","volume":"314","author":"D.A. Bayer","year":"1989","unstructured":"D.A. Bayer and J.C. Lagarias, \u201cThe nonlinear geometry of linear programming II. Legendre transform coordinates and central trajectories,\u201dTransactions of the American Mathematical Society 314 (1989) 527\u2013581.","journal-title":"Transactions of the American Mathematical Society"},{"key":"CR5","volume-title":"\u201cUsing an interior point method in a branch and bound algorithm for integer programming,\u201d Technical Report 195","author":"B. Borchers","year":"1991","unstructured":"B. Borchers and J.E. Mitchell, \u201cUsing an interior point method in a branch and bound algorithm for integer programming,\u201d Technical Report 195, Mathematical Sciences, Rensselaer Polytechnic Institute (Troy, NY, 1991)."},{"key":"CR6","doi-asserted-by":"crossref","first-page":"304","DOI":"10.1287\/ijoc.2.4.304","volume":"2","author":"In Chan Choi","year":"1990","unstructured":"In Chan Choi, C.L. Monma and D.F. Shanno, \u201cFurther development of a primal-dual interior point method,\u201dORSA Journal on Computing 2 (1990) 304\u2013311.","journal-title":"ORSA Journal on Computing"},{"key":"CR7","volume-title":"\u201cWorst-case analysis of a new heuristic for the traveling salesman problem,\u201d Technical report, GSIA","author":"N. Christofides","year":"1976","unstructured":"N. Christofides, \u201cWorst-case analysis of a new heuristic for the traveling salesman problem,\u201d Technical report, GSIA, Carnegie-Mellon University (Pittsburgh, 1976)."},{"key":"CR8","first-page":"339","volume-title":"Activity Analysis of Production and Allocation","author":"G.B. Dantzig","year":"1951","unstructured":"G.B. Dantzig, \u201cMaximization of a linear function of variables subject to linear inequalities,\u201d in: Tj.C. Koopmans, ed.,Activity Analysis of Production and Allocation (Wiley, New York, 1951) pp. 339\u2013347."},{"key":"CR9","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1007\/BF02240072","volume":"36","author":"U. Derigs","year":"1986","unstructured":"U. Derigs and A. Metz, \u201cOn the use of optimal fractional matchings for solving the (integer) matching problem,\u201dComputing 36 (1986) 263\u2013270.","journal-title":"Computing"},{"key":"CR10","doi-asserted-by":"crossref","first-page":"125","DOI":"10.6028\/jres.069B.013","volume":"69B","author":"J. Edmonds","year":"1965","unstructured":"J. Edmonds, \u201cMaximum matching and a polyhedron with 0, 1 vertices,\u201dJournal of Research National Bureau of Standards 69B (1965) 125\u2013130.","journal-title":"Journal of Research National Bureau of Standards"},{"key":"CR11","doi-asserted-by":"crossref","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J. Edmonds","year":"1965","unstructured":"J. Edmonds, \u201cPaths, trees and flowers,\u201dCanadian Journal of Mathematics 17 (1965) 449\u2013467.","journal-title":"Canadian Journal of Mathematics"},{"key":"CR12","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1007\/BF01582900","volume":"52","author":"R.M. Freund","year":"1991","unstructured":"R.M. Freund, \u201cA potential-function reduction algorithm for solving a linear program directly from an infeasible \u201cwarm start\u201d,\u201dMathematical Programming (Series B) 52 (1991) 441\u2013466.","journal-title":"Mathematical Programming (Series B)"},{"key":"CR13","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/BF02591685","volume":"37","author":"D.M. Gay","year":"1987","unstructured":"D.M. Gay, \u201cA variant of Karmarkar's linear programming algorithm for problems in standard form,\u201dMathematical Programming 37 (1987) 81\u201390.","journal-title":"Mathematical Programming"},{"key":"CR14","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/0024-3795(80)90159-7","volume":"34","author":"J.A. George","year":"1980","unstructured":"J.A. George and M.T. Heath, \u201cSolution of sparse linear least squares problems using Givens rotations,\u201dLinear Algebra and its Applications 34 (1980) 69\u201383.","journal-title":"Linear Algebra and its Applications"},{"key":"CR15","doi-asserted-by":"crossref","first-page":"460","DOI":"10.1137\/0907031","volume":"7","author":"J.A. George","year":"1986","unstructured":"J.A. George and E.G.Y. Ng, \u201cOrthogonal reduction of sparse matrices to upper triangular form using Householder transformations,\u201dSIAM Journal on Scientific and Statistical Computing 7 (1986) 460\u2013472.","journal-title":"SIAM Journal on Scientific and Statistical Computing"},{"key":"CR16","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/978-3-0348-9297-1_6","volume-title":"Trends in Mathematical Optimization, International Series of Numerical Mathematics No. 84","author":"J.-L. Goffin","year":"1988","unstructured":"J.-L. Goffin, \u201cAffine and projective transformations in non-differentiable optimization,\u201d in: K.-H. Hoffmann, J.-B. Hiriart-Urruty, C. Lemarechal and J. Zowe, eds.,Trends in Mathematical Optimization, International Series of Numerical Mathematics No. 84 (Birkhauser, Basel-Boston, 1988) pp. 79\u201391."},{"key":"CR17","volume-title":"\u201cDecomposition and nondifferentiable optimization with the projective algorithm,\u201d Technical Report 91-01-17","author":"J.-L. Goffin","year":"1990","unstructured":"J.-L. Goffin, A. Haurie and J.-P. Vial, \u201cDecomposition and nondifferentiable optimization with the projective algorithm,\u201d Technical Report 91-01-17, Faculty of Management, McGill University (Montreal, Que., 1990)."},{"key":"CR18","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1007\/BF00939559","volume":"65","author":"J.-L. Goffin","year":"1990","unstructured":"J.-L. Goffin and J.-P. Vial, \u201cCutting planes and column generation techniques with the projective algorithm,\u201dJournal of Optimization Theory and Applications 65 (1990) 409\u2013429.","journal-title":"Journal of Optimization Theory and Applications"},{"key":"CR19","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/S0927-0507(89)01003-0","volume-title":"Optimization","author":"D. Goldfarb","year":"1989","unstructured":"D. Goldfarb and M.J. Todd, \u201cLinear programming,\u201d in G.L. Nemhauser et al., eds.,Optimization (North-Holland, Amsterdam, 1989) Chapter 2, pp. 73\u2013170."},{"key":"CR20","volume-title":"Matrix Computations","author":"G.H. Golub","year":"1983","unstructured":"G.H. Golub and C.F. Van Loan,Matrix Computations (Johns Hopkins University Press, Baltimore, MD, 1983)."},{"key":"CR21","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1137\/0109047","volume":"9","author":"R.E. Gomory","year":"1961","unstructured":"R.E. Gomory and T.C. Hu, \u201cMulti terminal network flows,\u201dJournal of the Society for Industrial and Applied Mathematics 9 (1961) 551\u2013571.","journal-title":"Journal of the Society for Industrial and Applied Mathematics"},{"key":"CR22","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/BF01582287","volume":"43","author":"C.C. Gonzaga","year":"1989","unstructured":"C.C. Gonzaga, \u201cA conical projection algorithm for linear programming,\u201dMathematical Programming 43 (1989) 151\u2013174.","journal-title":"Mathematical Programming"},{"key":"CR23","unstructured":"M. Gr\u00f6tschel, Private Communication, 1987."},{"key":"CR24","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1007\/BF01584376","volume":"33","author":"M. Gr\u00f6tschel","year":"1985","unstructured":"M. Gr\u00f6tschel and O. Holland, \u201cSolving matching problems with linear programming,\u201dMathematical Programming 33 (1985) 243\u2013259.","journal-title":"Mathematical Programming"},{"key":"CR25","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/BF02579273","volume":"1","author":"M. Gr\u00f6tschel","year":"1981","unstructured":"M. Gr\u00f6tschel, L. Lovasz and A. Schrijver, \u201cThe ellipsoid method and its conseqeunces in combinatorial optimization,\u201dCombinatorica 1 (1981) 169\u2013197.","journal-title":"Combinatorica"},{"key":"CR26","doi-asserted-by":"crossref","first-page":"481","DOI":"10.1007\/BF01582902","volume":"52","author":"D. Hertog den","year":"1991","unstructured":"D. den Hertog and C. Roos, \u201cA survey of search directions in interior point methods for linear programming,\u201dMathematical Programming (Series B) 52 (1991) 481\u2013509.","journal-title":"Mathematical Programming (Series B)"},{"key":"CR27","unstructured":"IBM.IBM Optimization Subroutine Library Guide and Reference, Publication number SC23-0519-1 (1990)."},{"key":"CR28","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1007\/BF02579150","volume":"4","author":"N.K. Karmarkar","year":"1984","unstructured":"N.K. Karmarkar, \u201cA new polynomial-time algorithm for linear programming,\u201dCombinatorica 4 (1984) 373\u2013395.","journal-title":"Combinatorica"},{"key":"CR29","first-page":"297","volume-title":"Mathematical Developments Arising from Linear Programming, Contemporary Mathematics No. 114","author":"N.K. Karmarkar","year":"1991","unstructured":"N.K. Karmarkar, \u201cAn interior-point approach to NP-complete problems (Part I),\u201d in: J.C. Lagarias and M.J. Todd, eds.,Mathematical Developments Arising from Linear Programming, Contemporary Mathematics No. 114 (American Mathematical Society, Providence, RI, 1991) pp. 297\u2013308."},{"key":"CR30","doi-asserted-by":"crossref","first-page":"597","DOI":"10.1007\/BF01582907","volume":"52","author":"N.K. Karmarkar","year":"1991","unstructured":"N.K. Karmarkar, M.G.C. Resende and K.G. Ramakrishnan, \u201cAn interior point algorithm to solve computationally difficult set covering problems,\u201dMathematical Programming (Series B) 52 (1991) 597\u2013618.","journal-title":"Mathematical Programming (Series B)"},{"key":"CR31","doi-asserted-by":"crossref","first-page":"2245","DOI":"10.1002\/j.1538-7305.1965.tb04146.x","volume":"44","author":"S. Lin","year":"1965","unstructured":"S. Lin, \u201cComputer solutions to the traveling salesman problem,\u201dBell System Technical Journal 44 (1965) 2245\u20132269.","journal-title":"Bell System Technical Journal"},{"key":"CR32","volume-title":"Matching Theory","author":"L. Lov\u00e1sz","year":"1986","unstructured":"L. Lov\u00e1sz and M.D. Plummer,Matching Theory (Akad\u00e9miai Kiad\u00f3, Budapest, 1986)."},{"key":"CR33","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/0024-3795(91)90275-2","volume":"152","author":"I.J. Lustig","year":"1991","unstructured":"I.J. Lustig, R.E. Marsten and D.F. Shanno, \u201cComputational experience with a primal-dual interior point method for linear programming,\u201dLinear Algebra and its Applications 152 (1991) 191\u2013222.","journal-title":"Linear Algebra and its Applications"},{"key":"CR34","unstructured":"I.J. Lustig, R.E. Marsten and D.F. Shanno, \u201cOn implementating Mehrotra's predictor-corrector interior point method for linear programming,\u201d to appear in:SIAM Journal on Optimization."},{"key":"CR35","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1007\/978-1-4613-9617-8_8","volume-title":"Progress in Mathematical Programming","author":"N. Megiddo","year":"1989","unstructured":"N. Megiddo, \u201cPathways to the optimal set in linear programming,\u201d in: N. Megiddo, ed.,Progress in Mathematical Programming (Springer, New York, 1989) pp. 131\u2013158."},{"key":"CR36","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1287\/moor.14.1.97","volume":"14","author":"N. Megiddo","year":"1989","unstructured":"N. Megiddo and M. Shub, \u201cBoundary behaviour of interior point algorithms in linear programming,\u201dMathematics of Operations Research 14 (1989) 97\u2013146.","journal-title":"Mathematics of Operations Research"},{"key":"CR37","volume-title":"Karmarkar's Algorithm and Combinatorial Optimization Problems","author":"J.E. Mitchell","year":"1988","unstructured":"J.E. Mitchell,Karmarkar's Algorithm and Combinatorial Optimization Problems, Ph.D. thesis, School of Operations Research and Industrial Engineering, Cornell University (Ithaca, NY, 1988)."},{"key":"CR38","volume-title":"\u201cAn interior point column generation method for linear programming using shifted barriers,\u201d Technical Report 191","author":"J.E. Mitchell","year":"1990","unstructured":"J.E. Mitchell, \u201cAn interior point column generation method for linear programming using shifted barriers,\u201d Technical Report 191, Mathematical Sciences, Rensselaer Polytechnic Institute (Troy, NY, 1990)."},{"key":"CR39","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1137\/0610003","volume":"10","author":"J.E. Mitchell","year":"1989","unstructured":"J.E. Mitchell and M.J. Todd, \u201cA variant of Karmarkar's linear programming algorithm for problems with some unrestricted variables,\u201dSIAM Journal on Matrix Analysis and Applications 10 (1989) 30\u201338.","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"key":"CR40","first-page":"309","volume-title":"Mathematical Developments Arising from Linear Programming, Contemporary Mathematics No. 114","author":"J.E. Mitchell","year":"1991","unstructured":"J.E. Mitchell and M.J. Todd, \u201cSolving matching problems using Karmarkar's algorithm,\u201d in: J.C. Lagarias and M.J. Todd, eds.,Mathematical Developments Arising from Linear Programming, Contemporary Mathematics No. 114 (American Mathematical Society, Providence, RI, 1991) pp. 309\u2013318."},{"key":"CR41","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1287\/moor.7.1.67","volume":"7","author":"M.W. Padberg","year":"1982","unstructured":"M.W. Padberg and M.R. Rao, \u201cOdd minimum cut-sets andb-matchings,\u201dMathematics of Operations Research 7 (1982) 67\u201380.","journal-title":"Mathematics of Operations Research"},{"key":"CR42","volume-title":"Combinatorial Optimization: Algorithms and Complexity","author":"C.H. Papadimitriou","year":"1982","unstructured":"C.H. Papadimitriou and K. Steiglitz,Combinatorial Optimization: Algorithms and Complexity (Prentice-Hall, Englewood Cliffs, NJ, 1982)."},{"key":"CR43","unstructured":"SAS Institute, Inc, Cary, North Carolina,SAS User's Guide, Version 5 (1985)."},{"key":"CR44","volume-title":"An extension of Karmarkar's algorithm for bounded linear programming problems","author":"A.E. Steger","year":"1985","unstructured":"A.E. Steger, \u201cAn extension of Karmarkar's algorithm for bounded linear programming problems,\u201d Master's thesis, State University of New York at Stony Brook (Stony Brook, NY, 1985)."},{"key":"CR45","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, \u201cAn extension of Karmarkar's algorithm for linear programming using dual variables,\u201dAlgorithmica 1 (1986) 409\u2013424.","journal-title":"Algorithmica"},{"key":"CR46","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, \u201cA modification of Karmarkar's linear programming algorithm,\u201dAlgorithmica 1 (1986) 395\u2013407.","journal-title":"Algorithmica"},{"key":"CR47","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1137\/0802002","volume":"2","author":"Y. Ye","year":"1992","unstructured":"Y. Ye, \u201cA potential reduction algorithm allowing column generation,\u201dSIAM Journal on Optimization 2 (1992) 7\u201320.","journal-title":"SIAM Journal on Optimization"},{"key":"CR48","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1007\/BF02592079","volume":"39","author":"Y. Ye","year":"1987","unstructured":"Y. Ye and M. Kojima, \u201cRecovering optimal dual solutions in Karmarkar's polynomial algorithm for linear programming,\u201dMathematical Programming 39 (1987) 305\u2013317.","journal-title":"Mathematical Programming"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01580902.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01580902\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01580902","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T03:50:51Z","timestamp":1586231451000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01580902"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,8]]},"references-count":48,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[1992,8]]}},"alternative-id":["BF01580902"],"URL":"https:\/\/doi.org\/10.1007\/bf01580902","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,8]]}}}