{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T19:27:34Z","timestamp":1648754854381},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540645900","type":"print"},{"value":"9783540693468","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/3-540-69346-7_26","type":"book-chapter","created":{"date-parts":[[2007,8,2]],"date-time":"2007-08-02T11:51:29Z","timestamp":1186055489000},"page":"338-352","source":"Crossref","is-referenced-by-count":31,"title":["An Implementation of a Combinatorial Approximation Algorithm for Minimum-Cost Multicommodity Flow"],"prefix":"10.1007","author":[{"given":"Andrew V.","family":"Goldberg","sequence":"first","affiliation":[]},{"given":"Jeffrey D.","family":"Oldham","sequence":"additional","affiliation":[]},{"given":"Serge","family":"Plotkin","sequence":"additional","affiliation":[]},{"given":"Cliff","family":"Stein","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[1998,6,18]]},"reference":[{"key":"26_CR1","volume-title":"Network Flows: Theory, Algorithms, and Applications","author":"R. K. Ahuja","year":"1993","unstructured":"R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, Englewood Cliffs, NJ, 1993."},{"issue":"3","key":"26_CR2","doi-asserted-by":"publisher","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. Karmarkar. An implementation of Karmarkar\u2019s algorithm for linear programming. Mathematical Programming A, 44(3):297\u2013335, 1989.","journal-title":"Mathematical Programming A"},{"issue":"1","key":"26_CR3","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1002\/net.3230080107","volume":"8","author":"A. A. Assad","year":"1978","unstructured":"A. A. Assad. Multicommodity network flows \u2014 A survey. Networks, 8(1):37\u201391, Spring 1978.","journal-title":"Networks"},{"key":"26_CR4","unstructured":"T. Badics. genrmf. 1991. ftp:\/\/dimacs.rutgers.edu\/pub\/netflow\/generators\/network\/genrmf\/"},{"issue":"1","key":"26_CR5","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/0377-2217(95)00137-9","volume":"92","author":"J. Castro","year":"1996","unstructured":"J. Castro and N. Nabona. An implementation of linear and nonlinear multicommodity network flows. European Journal of Operational Research, 92(1):37\u201353, 1996.","journal-title":"European Journal of Operational Research"},{"key":"26_CR6","unstructured":"CPLEX Optimization, Inc., Incline Village, NV. Using the CPLEX Callable Library, 4.0 edition, 1995."},{"key":"26_CR7","volume-title":"Linear Programming and Extensions","author":"G. B. Dantzig","year":"1963","unstructured":"G. B. Dantzig. Linear Programming and Extensions. Princeton University Press, Princeton, NJ, 1963."},{"issue":"3","key":"26_CR8","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1007\/BF02592195","volume":"75","author":"M. D. Grigoriadis","year":"1996","unstructured":"M. D. Grigoriadis and L. G. Khachiyan. Approximate minimum-cost multicommodity flows in \u00d5(\u2208 \u22122 knm) time. Mathematical Programming, 75(3):477\u2013482, 1996.","journal-title":"Mathematical Programming"},{"issue":"5","key":"26_CR9","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/0020-0190(92)90032-Q","volume":"42","author":"A. V. Goldberg","year":"1992","unstructured":"A. V. Goldberg. A natural randomization strategy for multicommodity flow and related algorithms. Information Processing Letters, 42(5):249\u2013256, 1992.","journal-title":"Information Processing Letters"},{"key":"26_CR10","doi-asserted-by":"crossref","unstructured":"A. Goldberg, J. D. Oldham, S. Plotkin, and C. Stein. An implementation of a combinatorial approximation algorithm for minimum-cost multicommodity flow. Technical Report CS-TR-97-1600, Stanford University, December 1997.","DOI":"10.1007\/3-540-69346-7_26"},{"key":"26_CR11","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/BFb0121089","volume":"26","author":"M. D. Grigoriadis","year":"1986","unstructured":"M. D. Grigoriadis. An efficient implementation of the network simplex method. Mathematical Programming Study, 26:83\u2013111, 1986.","journal-title":"Mathematical Programming Study"},{"issue":"4","key":"26_CR12","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/S0968-090X(96)00012-5","volume":"4C","author":"R. W. Hall","year":"1996","unstructured":"R. W. Hall and D. Lotspeich. Optimized lane assignment on an automated highway. Transportation Research\u2014C, 4C(4):211\u2013229, 1996.","journal-title":"Transportation Research\u2014C"},{"issue":"3","key":"26_CR13","first-page":"231","volume":"30A","author":"A. Haghani","year":"1996","unstructured":"A. Haghani and S.-C. Oh. Formulation and solution of a multi-commodity, multi-modal network flow model for disaster relief operations. Transportation Research\u2014A, 30A(3):231\u2013250, 1996.","journal-title":"Transportation Research\u2014A"},{"issue":"4","key":"26_CR14","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/BF02579150","volume":"4","author":"N. Karmarkar","year":"1984","unstructured":"N. Karmarkar. A new polynomial-time algorithm for linear programming. Combinatorica, 4(4):373\u2013395, 1984.","journal-title":"Combinatorica"},{"key":"26_CR15","volume-title":"Algorithms for Network Programming","author":"J. L. Kennington","year":"1980","unstructured":"J. L. Kennington and R. V. Helgason. Algorithms for Network Programming. John Wiley & Sons, New York, 1980."},{"issue":"1","key":"26_CR16","first-page":"51","volume":"20","author":"L. G. Khachiyan","year":"1980","unstructured":"L. G. Khachiyan. Polynomial algorithms in linear programming. Zhurnal Vychislitel\u2019noi Matematiki i Matematicheskoi Fiziki (Journal of Computational Mathematics and Mathematical Physics), 20(1):51\u201368, 1980.","journal-title":"Zhurnal Vychislitel\u2019noi Matematiki i Matematicheskoi Fiziki"},{"key":"26_CR17","first-page":"502","volume":"6","author":"A. Kamath","year":"1995","unstructured":"A. Kamath and O. Palmon. Improved interior point algorithms for exact and approximate solution of multicommodity flow problems. In Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, Vol. 6, pages 502\u2013511. Association for Computing Machinery, January 1995.","journal-title":"Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms"},{"key":"26_CR18","first-page":"18","volume":"27","author":"D. Karger","year":"1995","unstructured":"D. Karger and S. Plotkin. Adding multiple cost constraints to combinatorial optimization problems, with applications to multicommodity flows. In Symposium on the Theory of Computing, Vol. 27, pages 18\u201325. Association for Computing Machinery, ACM Press, May 1995.","journal-title":"Symposium on the Theory of Computing"},{"issue":"3","key":"26_CR19","doi-asserted-by":"publisher","first-page":"466","DOI":"10.1137\/S0097539792241175","volume":"23","author":"P. Klein","year":"1994","unstructured":"P. Klein, S. Plotkin, C. Stein, and \u00c9. Tardos. Faster approximation algorithms for the unit capacity concurrent flow problem with applications to routing and finding sparse cuts. SIAM Journal on Computing, 23(3):466\u2013487, 1994.","journal-title":"SIAM Journal on Computing"},{"key":"26_CR20","first-page":"147","volume":"18","author":"S. Kapoor","year":"1986","unstructured":"S. Kapoor and P. M. Vaidya. Fast algorithms for convex quadratic programming and multicommodity flows. In Proceedings of the 18th Annual ACM Symposium on Theory of Computing, Vol. 18, pages 147\u2013159. Association for Computing Machinery, 1986.","journal-title":"Proceedings of the 18th Annual ACM Symposium on Theory of Computing"},{"issue":"2","key":"26_CR21","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1006\/jcss.1995.1020","volume":"50","author":"L.M.P.+.9.5._.T. Leighton","year":"1995","unstructured":"LMP+95._T. Leighton, F. Makedon, S. Plotkin, C. Stein, \u00c9. Tardos, and S. Tragoudas. Fast approximation algorithms for multicommodity flow problems. Journal of Computer and System Sciences, 50(2):228\u2013243, 1995.","journal-title":"Journal of Computer and System Sciences"},{"key":"26_CR22","unstructured":"Y. Lee and J. Orlin. GRIDGEN. 1991. ftp:\/\/dimacs.rutgers.edu\/pub\/netflow\/generators\/network\/gridgen\/"},{"key":"26_CR23","doi-asserted-by":"crossref","unstructured":"T. Leong, P. Shor, and C. Stein. Implementation of a combinatorial multicommodity flow algorithm. In David S. Johnson and Catherine C. Mc-Geoch, editors, Network Flows and Matching, Series in Discrete Mathematics and Theoretical Computer Science, Vol. 12, pages 387\u2013405. American Mathematical Society, 1993.","DOI":"10.1090\/dimacs\/012\/15"},{"key":"26_CR24","volume-title":"Numerical Recipes in C","author":"W. H. Press","year":"1988","unstructured":"W. H. Press, B. P. Flannery, S. A. Teukolsky, and W. T. Vetterling. Numerical Recipes in C. Cambridge University Press, Cambridge, 1988."},{"issue":"2","key":"26_CR25","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1287\/moor.20.2.257","volume":"20","author":"S. A. Plotkin","year":"1995","unstructured":"S. A. Plotkin, D. B. Shmoys, and \u00c9. Tardos. Fast approximation algorithms for fractional packing and covering problems. Mathematics of Operations Research, 20(2):257\u2013301, 1995.","journal-title":"Mathematics of Operations Research"},{"issue":"1","key":"26_CR26","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/BF02614505","volume":"78","author":"T. Radzik","year":"1997","unstructured":"T. Radzik. Fast deterministic approximation for the multicommodity flow problem. Mathematical Programming, 78(1):43\u201358, 1997.","journal-title":"Mathematical Programming"},{"key":"26_CR27","volume-title":"Analysis \u00c6quationum Universalis, seu, Ad \u00c6quationes Algebraicas Resolvendas Methodus Generalis, et Expedita","author":"J. Raphson","year":"1690","unstructured":"J. Raphson. Analysis \u00c6quationum Universalis, seu, Ad \u00c6quationes Algebraicas Resolvendas Methodus Generalis, et Expedita. Prostant venales apud Abelem Swalle, London, 1690."},{"key":"26_CR28","volume-title":"Scaling Algorithms for Multicommodity Flow Problems and Network Flow Problems with Side Constraints","author":"R. Schneur","year":"1991","unstructured":"R. Schneur. Scaling Algorithms for Multicommodity Flow Problems and Network Flow Problems with Side Constraints. PhD thesis, MIT, Cambridge, MA, February 1991."},{"key":"26_CR29","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1109\/SFCS.1989.63499","volume":"30","author":"P. M. Vaidya","year":"1989","unstructured":"P. M. Vaidya. Speeding up linear programming using fast matrix multiplication. In Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Vol. 30, pages 332\u2013337. IEEE Computer Society Press, 1989.","journal-title":"Proceedings of the 30th Annual Symposium on Foundations of Computer Science"}],"container-title":["Integer Programming and Combinatorial Optimization","Lecture Notes in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-69346-7_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T14:06:22Z","timestamp":1556719582000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-69346-7_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540645900","9783540693468"],"references-count":29,"URL":"http:\/\/dx.doi.org\/10.1007\/3-540-69346-7_26","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"published":{"date-parts":[[1998]]}}}