{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T05:57:05Z","timestamp":1743141425627,"version":"3.40.3"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319213972"},{"type":"electronic","value":"9783319213989"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-21398-9_55","type":"book-chapter","created":{"date-parts":[[2015,6,23]],"date-time":"2015-06-23T15:12:41Z","timestamp":1435072361000},"page":"701-712","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Smoothed Analysis of the Minimum-Mean Cycle Canceling Algorithm and the Network Simplex Algorithm"],"prefix":"10.1007","author":[{"given":"Kamiel","family":"Cornelissen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bodo","family":"Manthey","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,24]]},"reference":[{"key":"55_CR1","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin. J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice-Hall (1993)"},{"issue":"3","key":"55_CR2","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1016\/j.jcss.2004.04.004","volume":"69","author":"R Beier","year":"2004","unstructured":"Beier, R., V\u00f6cking, B.: Random knapsack in expected polynomial time. Journal of Computer and System Sciences 69(3), 306\u2013329 (2004)","journal-title":"Journal of Computer and System Sciences"},{"key":"55_CR3","doi-asserted-by":"crossref","unstructured":"Brunsch, T., Cornelissen, K., Manthey, B., R\u00f6glin, H., R\u00f6sner, C.: Smoothed analysis of the successive shortest path algorithm. Computing Research Repository 1501.05493 [cs.DS], arXiv 2015. Preliminary version at SODA (2013)","DOI":"10.1137\/1.9781611973105.85"},{"key":"55_CR4","doi-asserted-by":"crossref","unstructured":"Busacker, R.G., Gowen, P.J.: A procedure for determining a family of miminum-cost network flow patterns. Technical Report Technical Paper 15, Operations Research Office (1960)","DOI":"10.21236\/AD0249662"},{"key":"55_CR5","doi-asserted-by":"crossref","unstructured":"Dantzig, G.B.: Linear programming and extensions. Rand Corporation Research Study. Princeton Univ. Press, Princeton (1963)","DOI":"10.7249\/R366"},{"issue":"2","key":"55_CR6","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1145\/321694.321699","volume":"19","author":"J Edmonds","year":"1972","unstructured":"Edmonds, J., Karp, R.M.: Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM 19(2), 248\u2013264 (1972)","journal-title":"Journal of the ACM"},{"key":"55_CR7","doi-asserted-by":"crossref","unstructured":"Ford, Jr. L.R., Fulkerson, D.R.: Flows in Networks. Princeton University Press (1962)","DOI":"10.1515\/9781400875184"},{"issue":"1","key":"55_CR8","first-page":"18","volume":"9","author":"DR Fulkerson","year":"1961","unstructured":"Fulkerson, D.R.: An out-of-kilter algorithm for minimal cost flow problems. Journal of the SIAM 9(1), 18\u201327 (1961)","journal-title":"Journal of the SIAM"},{"key":"55_CR9","doi-asserted-by":"crossref","unstructured":"Goldberg, A.V., Tarjan, R.E.: Finding minimum-cost circulations by canceling negative cycles. J. ACM 36(4), 873\u2013886 (1989)","DOI":"10.1145\/76359.76368"},{"key":"55_CR10","unstructured":"Iri, M.: A new method for solving transportation-network problems. Journal of the Operations Research Society of Japan 3(1,2), 27\u201387 (1960)"},{"issue":"4","key":"55_CR11","doi-asserted-by":"publisher","first-page":"476","DOI":"10.1287\/opre.10.4.476","volume":"10","author":"WS Jewell","year":"1962","unstructured":"Jewell, W.S.: Optimal flow through networks. Operations Research 10(4), 476\u2013499 (1962)","journal-title":"Operations Research"},{"issue":"3","key":"55_CR12","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0012-365X(78)90011-0","volume":"23","author":"RM Karp","year":"1978","unstructured":"Karp, R.M.: A characterization of the minimum cycle mean in a digraph. Discrete Mathematics 23(3), 309\u2013311 (1978)","journal-title":"Discrete Mathematics"},{"issue":"3","key":"55_CR13","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1287\/mnsc.14.3.205","volume":"14","author":"M Klein","year":"1967","unstructured":"Klein, M.: A primal method for minimal cost flows with applications to the assignment and transportation problems. Management Science 14(3), 205\u2013220 (1967)","journal-title":"Management Science"},{"key":"55_CR14","unstructured":"Korte, B., Vygen, J.: Combinatorial Optimization: Theory and Algorithms, 1st edn. Springer Publishing Company, Incorporated (2007)"},{"issue":"1","key":"55_CR15","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1080\/10556788.2014.895828","volume":"30","author":"P Kov\u00e1cs","year":"2015","unstructured":"Kov\u00e1cs, P.: Minimum-cost flow algorithms: An experimental evaluation. Optimization Methods and Software 30(1), 94\u2013127 (2015)","journal-title":"Optimization Methods and Software"},{"key":"55_CR16","doi-asserted-by":"crossref","unstructured":"Manthey, B., R\u00f6glin, H.: Smoothed analysis: Analysis of algorithms beyond worst case. it - Information Technology 53(6), 280\u2013286 (2011)","DOI":"10.1524\/itit.2011.0654"},{"key":"55_CR17","doi-asserted-by":"crossref","unstructured":"Minty, G.J.: Monotone networks. In Proceedings of the Royal Society of London A, pp. 194\u2013212 (1960)","DOI":"10.1098\/rspa.1960.0144"},{"key":"55_CR18","unstructured":"Orlin, J.B.: Genuinely polynomial simplex and non-simplex algorithms for the minimum cost flow problem. Technical report, Sloan School of Management. MIT, Cambridge, Technical Report No. 1615\u201384 (1984)"},{"issue":"2","key":"55_CR19","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1287\/opre.41.2.338","volume":"41","author":"JB Orlin","year":"1993","unstructured":"Orlin, J.B.: A faster strongly polynomial minimum cost flow algorithm. Operations Research 41(2), 338\u2013350 (1993)","journal-title":"Operations Research"},{"key":"55_CR20","first-page":"109","volume":"77","author":"JB Orlin","year":"1997","unstructured":"Orlin, J.B.: A polynomial time primal network simplex algorithm for minimum cost flows. Math. Program. 77, 109\u2013129 (1997)","journal-title":"Math. Program."},{"issue":"3","key":"55_CR21","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1007\/BF01240734","volume":"11","author":"T Radzik","year":"1994","unstructured":"Radzik, T., Goldberg, A.V.: Tight bounds on the number of minimum-mean cycle cancellations and related results. Algorithmica 11(3), 226\u2013242 (1994)","journal-title":"Algorithmica"},{"issue":"3","key":"55_CR22","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1145\/990308.990310","volume":"51","author":"DA Spielman","year":"2004","unstructured":"Spielman, D.A., Teng, S.-H.: Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. J. ACM 51(3), 385\u2013463 (2004)","journal-title":"J. ACM"},{"issue":"10","key":"55_CR23","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1145\/1562764.1562785","volume":"52","author":"DA Spielman","year":"2009","unstructured":"Spielman, D.A., Teng, S.-H.: Smoothed analysis: an attempt to explain the behavior of algorithms in practice. Communications of the ACM 52(10), 76\u201384 (2009)","journal-title":"Communications of the ACM"},{"issue":"3","key":"55_CR24","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/BF02579369","volume":"5","author":"\u00c9 Tardos","year":"1985","unstructured":"Tardos, \u00c9.: A strongly polynomial minimum cost circulation algorithm. Combinatorica 5(3), 247\u2013256 (1985)","journal-title":"Combinatorica"},{"issue":"1","key":"55_CR25","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/BF01580132","volume":"5","author":"N Zadeh","year":"1973","unstructured":"Zadeh, N.: A bad network problem for the simplex method and other minimum cost flow algorithms. Mathematical Programming 5(1), 255\u2013266 (1973)","journal-title":"Mathematical Programming"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-21398-9_55","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,10]],"date-time":"2023-02-10T10:42:38Z","timestamp":1676025758000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-21398-9_55"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319213972","9783319213989"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-21398-9_55","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"24 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}