{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,10]],"date-time":"2026-11-10T21:03:30Z","timestamp":1794344610964,"version":"4.9.0"},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540695134","type":"print"},{"value":"9783540695141","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007]]},"DOI":"10.1007\/11970125_4","type":"book-chapter","created":{"date-parts":[[2007,1,24]],"date-time":"2007-01-24T00:47:40Z","timestamp":1169599660000},"page":"43-54","source":"Crossref","is-referenced-by-count":0,"title":["Online Dynamic Programming Speedups"],"prefix":"10.1007","author":[{"given":"Amotz","family":"Bar-Noy","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mordecai J.","family":"Golin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yan","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"issue":"2","key":"4_CR1","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0166-218X(95)00103-X","volume":"70","author":"R.E. Burkard","year":"1996","unstructured":"Burkard, R.E., Klinz, B., Rudolf, R.: Perspectives of Monge properties in optimization. Discrete Applied Mathematics\u00a070(2), 95\u2013161 (1996)","journal-title":"Discrete Applied Mathematics"},{"key":"4_CR2","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/BF01840359","volume":"2","author":"A. Aggarwal","year":"1987","unstructured":"Aggarwal, A., Klawe, M.M., Moran, S., Shor, P.W., Wilber, R.E.: Geometric applications of a matrix-searching algorithm. Algorithmica\u00a02, 195\u2013208 (1987)","journal-title":"Algorithmica"},{"issue":"3","key":"4_CR3","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1016\/0196-6774(88)90032-6","volume":"9","author":"R. Wilber","year":"1988","unstructured":"Wilber, R.: The concave least-weight subsequence problem revisited. Journal of Algorithms\u00a09(3), 418\u2013425 (1988)","journal-title":"Journal of Algorithms"},{"key":"4_CR4","doi-asserted-by":"crossref","unstructured":"Eppstein, D., Galil, Z., Giancarlo, R.: Speeding up dynamic programming. In: Proceedings of the 29th Annual Symposium on Foundations of Computer Science, pp. 488\u2013496 (1988)","DOI":"10.1109\/SFCS.1988.21965"},{"issue":"1","key":"4_CR5","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/0304-3975(89)90101-1","volume":"64","author":"Z. Galil","year":"1989","unstructured":"Galil, Z., Giancarlo, R.: Speeding up dynamic programming with applications to molecular biology. Theoretical Computer Science\u00a064(1), 107\u2013118 (1989)","journal-title":"Theoretical Computer Science"},{"issue":"6","key":"4_CR6","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0020-0190(90)90215-J","volume":"33","author":"Z. Galil","year":"1990","unstructured":"Galil, Z., Park, K.: A linear-time algorithm for concave one-dimensional dynamic programming. Information Processing Letters\u00a033(6), 309\u2013311 (1990)","journal-title":"Information Processing Letters"},{"issue":"3","key":"4_CR7","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1016\/0196-6774(91)90016-R","volume":"12","author":"L.L. Larmore","year":"1991","unstructured":"Larmore, L.L., Schieber, B.: On-line dynamic programming with applications to the prediction of RNA secondary structure. Journal of Algorithms\u00a012(3), 490\u2013515 (1991)","journal-title":"Journal of Algorithms"},{"issue":"3","key":"4_CR8","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/S0167-6377(00)00041-9","volume":"27","author":"G.J. Woeginger","year":"2000","unstructured":"Woeginger, G.J.: Monge strikes again: Optimal placement of web proxies in the Internet. Operations Research Letters\u00a027(3), 93\u201396 (2000)","journal-title":"Operations Research Letters"},{"issue":"4","key":"4_CR9","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1007\/s00453-005-1195-5","volume":"45","author":"R. Fleischer","year":"2006","unstructured":"Fleischer, R., Golin, M.J., Zhang, Y.: Online maintenance of k-medians and k-covers on a line. Algorithmica\u00a045(4), 549\u2013567 (2006)","journal-title":"Algorithmica"},{"issue":"2","key":"4_CR10","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1023\/B:WINE.0000013077.52762.94","volume":"10","author":"B. Krishnamachari","year":"2004","unstructured":"Krishnamachari, B., Gau, R.H., Wicker, S.B., Haas, Z.J.: Optimal sequential paging in cellular wireless networks. Wireless networks\u00a010(2), 121\u2013131 (2004)","journal-title":"Wireless networks"},{"key":"4_CR11","unstructured":"Bar-Noy, A., Feng, Y., Golin, M.J.: Efficiently paging mobile users under delay constraints (2006) (Unpublished manuscript)"}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11970125_4.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T03:23:54Z","timestamp":1619493834000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11970125_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540695134","9783540695141"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/11970125_4","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/11970125","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007]]}}}