{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:47Z","timestamp":1740109307144,"version":"3.37.3"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2019,8,8]],"date-time":"2019-08-08T00:00:00Z","timestamp":1565222400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,8,8]],"date-time":"2019-08-08T00:00:00Z","timestamp":1565222400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,2]]},"DOI":"10.1007\/s00453-019-00615-3","type":"journal-article","created":{"date-parts":[[2019,8,8]],"date-time":"2019-08-08T08:16:21Z","timestamp":1565252181000},"page":"300-315","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the Convergence Time of a Natural Dynamics for Linear Programming"],"prefix":"10.1007","volume":"82","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9038-6901","authenticated-orcid":false,"given":"Vincenzo","family":"Bonifaci","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,8,8]]},"reference":[{"key":"615_CR1","doi-asserted-by":"publisher","DOI":"10.1007\/978-4-431-55978-8","volume-title":"Information Geometry and Its Applications","author":"S Amari","year":"2016","unstructured":"Amari, S.: Information Geometry and Its Applications. Springer, Berlin (2016)"},{"issue":"1","key":"615_CR2","doi-asserted-by":"publisher","first-page":"121","DOI":"10.4086\/toc.2012.v008a006","volume":"8","author":"S Arora","year":"2012","unstructured":"Arora, S., Hazan, E., Kale, S.: The multiplicative weights update method: a meta-algorithm and applications. Theory Comput. 8(1), 121\u2013164 (2012)","journal-title":"Theory Comput."},{"key":"615_CR3","first-page":"499","volume":"314","author":"DA Bayer","year":"1989","unstructured":"Bayer, D.A., Lagarias, J.C.: The nonlinear geometry of linear programming, I. Affine and projective scaling trajectories. Trans. Am. Math. Soc. 314, 499\u2013526 (1989)","journal-title":"Trans. Am. Math. Soc."},{"key":"615_CR4","doi-asserted-by":"crossref","unstructured":"Becchetti, L., Bonifaci, V., Dirnberger, M., Karrenbauer, A., Mehlhorn, K.: Physarum can compute shortest paths: convergence proofs and complexity bounds. In: Proceedings of the 40th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science, vol. 7966, pp. 472\u2013483. Springer (2013)","DOI":"10.1007\/978-3-642-39212-2_42"},{"issue":"3","key":"615_CR5","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/S0167-6377(02)00231-6","volume":"31","author":"A Beck","year":"2003","unstructured":"Beck, A., Teboulle, M.: Mirror descent and nonlinear projected subgradient methods for convex optimization. Oper. Res. Lett. 31(3), 167\u2013175 (2003)","journal-title":"Oper. Res. Lett."},{"key":"615_CR6","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0619-4","volume-title":"Modern Graph Theory","author":"B Bollob\u00e1s","year":"1998","unstructured":"Bollob\u00e1s, B.: Modern Graph Theory. Springer, New York (1998)"},{"issue":"1\u20132","key":"615_CR7","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1016\/j.ipl.2012.09.005","volume":"113","author":"V Bonifaci","year":"2013","unstructured":"Bonifaci, V.: Physarum can compute shortest paths: a short proof. Inf. Process. Lett. 113(1\u20132), 4\u20137 (2013)","journal-title":"Inf. Process. Lett."},{"key":"615_CR8","unstructured":"Bonifaci, V.: On the convergence time of a natural dynamics for linear programming. In 28th International Symposium on Algorithms and Computation, ISAAC 2017, pp. 17:1\u201317:12. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik (2017)"},{"key":"615_CR9","doi-asserted-by":"crossref","unstructured":"Bonifaci, V., Mehlhorn, K., Varma, G.: Physarum can compute shortest paths. In: Proceedings of the 23rd ACM-SIAM Symposium on Discrete Algorithms, pp. 233\u2013240. SIAM (2012)","DOI":"10.1137\/1.9781611973099.21"},{"issue":"12","key":"615_CR10","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1145\/2380656.2380679","volume":"55","author":"B Chazelle","year":"2012","unstructured":"Chazelle, B.: Natural algorithms and influence systems. Commun. ACM 55(12), 101\u2013110 (2012)","journal-title":"Commun. ACM"},{"key":"615_CR11","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139173179","volume-title":"Evolutionary Games and Population Dynamics","author":"J Hofbauer","year":"1998","unstructured":"Hofbauer, J., Sigmund, K.: Evolutionary Games and Population Dynamics. Cambridge University Press, Cambridge (1998)"},{"key":"615_CR12","unstructured":"Ito, K., Johansson, A., Nakagaki, T., Tero, A.: Convergence properties for the Physarum solver. \narXiv:1101.5249v1\n\n (2011)"},{"key":"615_CR13","doi-asserted-by":"crossref","unstructured":"Johannson, A., Zou, J.Y.: A slime mold solver for linear programming problems. In: How the World Computes\u2014Turing Centenary Conference and 8th Conference on Computability in Europe, pp. 344\u2013354. Springer (2012)","DOI":"10.1007\/978-3-642-30870-3_35"},{"key":"615_CR14","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1090\/conm\/114\/1097865","volume-title":"Mathematical Developments Arising from Linear Programming, Contemporary Mathematics","author":"NK Karmarkar","year":"1990","unstructured":"Karmarkar, N.K.: Riemannian geometry underlying interior-point methods for linear programming. In: Lagarias, J.C., Todd, M.J. (eds.) Mathematical Developments Arising from Linear Programming, Contemporary Mathematics, vol. 114, pp. 51\u201375. American Mathematical Society, Providence (1990)"},{"key":"615_CR15","doi-asserted-by":"publisher","first-page":"470","DOI":"10.1038\/35035159","volume":"407","author":"T Nakagaki","year":"2000","unstructured":"Nakagaki, T., Yamada, H., T\u00f3th, \u00c1.: Maze-solving by an amoeboid organism. Nature 407, 470 (2000)","journal-title":"Nature"},{"key":"615_CR16","doi-asserted-by":"publisher","first-page":"546","DOI":"10.1038\/msb.2011.78","volume":"7","author":"S Navlakha","year":"2011","unstructured":"Navlakha, S., Bar-Joseph, Z.: Algorithms in nature: the convergence of systems biology and computational thinking. Mol. Syst. Biol. 7, 546 (2011)","journal-title":"Mol. Syst. Biol."},{"key":"615_CR17","volume-title":"Problem complexity and method efficiency in optimization","author":"AS Nemirovski","year":"1983","unstructured":"Nemirovski, A.S., Yudin, D.B.: Problem complexity and method efficiency in optimization. Wiley, Hoboken (1983)"},{"issue":"3","key":"615_CR18","doi-asserted-by":"publisher","first-page":"1451","DOI":"10.1109\/TIT.2015.2388583","volume":"61","author":"G Raskutti","year":"2015","unstructured":"Raskutti, G., Mukherjee, S.: The information geometry of mirror descent. IEEE Trans. Inf. Theory 61(3), 1451\u20131457 (2015)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"615_CR19","doi-asserted-by":"crossref","unstructured":"Straszak, D., Vishnoi, N.K.: Natural algorithms for flow problems. In: Proceedings of the 27th ACM-SIAM Symposium on Discrete Algorithms, pp. 1868\u20131883. SIAM (2016)","DOI":"10.1137\/1.9781611974331.ch131"},{"key":"615_CR20","doi-asserted-by":"crossref","unstructured":"Straszak, D., Vishnoi, N.K.: On a natural dynamics for linear programming. In: Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, pp. 291. ACM (2016)","DOI":"10.1145\/2840728.2840762"},{"key":"615_CR21","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/j.physa.2006.01.053","volume":"363","author":"A Tero","year":"2006","unstructured":"Tero, A., Kobayashi, R., Nakagaki, T.: Physarum solver: a biologically inspired method of road-network navigation. Physica A 363, 115\u2013119 (2006)","journal-title":"Physica A"},{"key":"615_CR22","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1016\/j.jtbi.2006.07.015","volume":"244","author":"A Tero","year":"2007","unstructured":"Tero, A., Kobayashi, R., Nakagaki, T.: A mathematical model for adaptive transport network in path finding by true slime mold. J. Theor. Biol. 244, 553\u2013564 (2007)","journal-title":"J. Theor. Biol."},{"key":"615_CR23","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1126\/science.1177894","volume":"327","author":"A Tero","year":"2010","unstructured":"Tero, A., Takagi, S., Saigusa, T., Ito, K., Bebber, D.P., Fricker, M.D., Yumiki, K., Kobayashi, R., Nakagaki, T.: Rules for biologically inspired adaptive network design. Science 327, 439\u2013442 (2010)","journal-title":"Science"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00615-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00615-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00615-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,8,6]],"date-time":"2020-08-06T23:19:34Z","timestamp":1596755974000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00615-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,8,8]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,2]]}},"alternative-id":["615"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00615-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2019,8,8]]},"assertion":[{"value":"17 January 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 July 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 August 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}