{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:04:49Z","timestamp":1750694689077},"reference-count":12,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1996,12,1]],"date-time":"1996-12-01T00:00:00Z","timestamp":849398400000},"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":[[1996,12]]},"DOI":"10.1007\/bf02592195","type":"journal-article","created":{"date-parts":[[2007,3,29]],"date-time":"2007-03-29T15:56:39Z","timestamp":1175183799000},"page":"477-482","source":"Crossref","is-referenced-by-count":15,"title":["Approximate minimum-cost multicommodity flows in $$\\tilde O$$ (\u025b \u22122 KNM) timetime"],"prefix":"10.1007","volume":"75","author":[{"given":"Michael D.","family":"Grigoriadis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leonid G.","family":"Khachiyan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF02592195_CR1","volume-title":"Network Flows","author":"R.K. Ahuja","year":"1993","unstructured":"R.K. Ahuja, T.L. Magnanti and J.B. Orlin,Network Flows (Prentice-Hall, Englewood Cliffs, NJ, 1993)."},{"key":"BF02592195_CR2","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1287\/trsc.12.4.277","volume":"12","author":"F. Glover","year":"1978","unstructured":"F. Glover, D. Karney, D. Klingman and R. Rusell, Solving singly constrained transshipment problems,Transportation Science 12 (1978) 277\u2013297.","journal-title":"Transportation Science"},{"key":"BF02592195_CR3","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1137\/0804004","volume":"4","author":"M.D. Grigoriadis","year":"1994","unstructured":"M.D. Grigoriadis and L.G. Khachiyan, Fast approximation schemes for convex programs with many blocks and coupling constraints,SIAM J. Optimization 4 (1994) 86\u2013107.","journal-title":"SIAM J. Optimization"},{"key":"BF02592195_CR4","series-title":"Tech. Rept. 94-19","volume-title":"Coordination complexity of parallel price-directive decomposition","author":"M.D. Grigoriadis","year":"1994","unstructured":"M.D. Grigoriadis and L.G. Khachiyan. Coordination complexity of parallel price-directive decomposition, Tech. Rept. 94-19, DIMACS, Rutgers University, New Brunswick, NJ, 1994,Mathematics of Operations Research 21(2) (1996) 321\u2013340."},{"key":"BF02592195_CR5","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/0020-0190(92)90032-Q","volume":"42","author":"A. Goldberg","year":"1992","unstructured":"A. Goldberg, A natural randomization strategy for multicommodity flow and related problems,Information Processing Letters 42 (1992) 249\u2013256.","journal-title":"Information Processing Letters"},{"key":"BF02592195_CR6","doi-asserted-by":"crossref","first-page":"430","DOI":"10.1287\/moor.15.3.430","volume":"15","author":"A. Goldberg","year":"1990","unstructured":"A. Goldberg and R.E. Tarjan, Solving minimum cost flow problems by successive approximation,Mathematics of Operations Research 15 (1990) 430\u2013466.","journal-title":"Mathematics of Operations Research"},{"key":"BF02592195_CR7","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1006\/jcss.1995.1020","volume":"50","author":"T. Leighton","year":"1995","unstructured":"T. Leighton, F. Makedon, S. Plotkin, C. Stein, E. Tardos and S. Tragoudas, Fast approximation algorithms for multicommodity flow problems,J. Computer and System Sciences 50 (1995) 228\u2013243: see also:Proc. 23rd Ann. ACM Symp. on Theory of Computing (1991) 101\u2013111.","journal-title":"J. Computer and System Sciences"},{"key":"BF02592195_CR8","doi-asserted-by":"crossref","unstructured":"D. Karger and S.A. Plotkin, Adding multiple cost constraints to combinatorial optimization problems with applications to multicommodity flows, in:Proc. 27th Annual ACM Symp. on Theory of Computing (1995) 18\u201325.","DOI":"10.1145\/225058.225073"},{"key":"BF02592195_CR9","unstructured":"A. Kamath, O. Palmon and S. Plotkin, Fast approximation algorithm for min-cost multicommodity flow, in:Proc. 6th ACM-SIAM Symp. on Discrete Algorithms (1995) 493\u2013501."},{"key":"BF02592195_CR10","doi-asserted-by":"crossref","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 E. Tardos, Fast approximation algorithms for fractional packing and covering problems,Mathematics of Operation Research 20 (1995) 257\u2013301; see also:Proc. 32nd Ann. Symp. on Foundations of Computer Science (1991) 495\u2013504.","journal-title":"Mathematics of Operation Research"},{"key":"BF02592195_CR11","unstructured":"T. Radzik, Fast deterministic approximation for the multicommodity flow problem, in:Proc. 6th ACM-SIAM Symp. on Discrete Algorithms (1995) 486\u2013492."},{"key":"BF02592195_CR12","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1007\/978-3-642-99789-1_25","volume-title":"Applied Mathematics and Parallel Computing\u2014Festschrift for Klaus Ritter","author":"J. Villavicencio","year":"1996","unstructured":"J. Villavicencio and M.D. Grigoriadis, Appr descent, in: H. Fischer, B. Riedm\u00fcller and S. Sch\u00e4ffler, eds.,Applied Mathematics and Parallel Computing\u2014Festschrift for Klaus Ritter (Physica-Verlag, Heidelberg, 1996) 359\u2013371; also: Tech. Rept. LCSR-TR-255, Dept. of Computer Science, Rutgers University, New Brunswick, NJ."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02592195.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02592195\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02592195","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,20]],"date-time":"2019-05-20T23:37:53Z","timestamp":1558395473000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02592195"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,12]]},"references-count":12,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1996,12]]}},"alternative-id":["BF02592195"],"URL":"https:\/\/doi.org\/10.1007\/bf02592195","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,12]]}}}