{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:00Z","timestamp":1740109320681,"version":"3.37.3"},"reference-count":11,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2022,1,27]],"date-time":"2022-01-27T00:00:00Z","timestamp":1643241600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,27]],"date-time":"2022-01-27T00:00:00Z","timestamp":1643241600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1070\/20)"],"award-info":[{"award-number":["1070\/20)"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100011199","name":"FP7 Ideas: European Research Council","doi-asserted-by":"publisher","award":["850979"],"award-info":[{"award-number":["850979"]}],"id":[{"id":"10.13039\/100011199","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,5]]},"DOI":"10.1007\/s00453-022-00928-w","type":"journal-article","created":{"date-parts":[[2022,1,27]],"date-time":"2022-01-27T07:02:31Z","timestamp":1643266951000},"page":"1341-1356","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Faster Minimization of Tardy Processing Time on a Single Machine"],"prefix":"10.1007","volume":"84","author":[{"given":"Karl","family":"Bringmann","sequence":"first","affiliation":[]},{"given":"Nick","family":"Fischer","sequence":"additional","affiliation":[]},{"given":"Danny","family":"Hermelin","sequence":"additional","affiliation":[]},{"given":"Dvir","family":"Shabtay","sequence":"additional","affiliation":[]},{"given":"Philip","family":"Wellnitz","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,1,27]]},"reference":[{"key":"928_CR1","doi-asserted-by":"crossref","unstructured":"Abboud, A., Bringmann, K., Hermelin, D., Shabtay, D.: SETH-based lower bounds for subset sum and bicriteria path. In: Proceedings of of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 41\u201357 (2019)","DOI":"10.1137\/1.9781611975482.3"},{"key":"928_CR2","doi-asserted-by":"crossref","unstructured":"Bringmann, K.: A near-linear pseudopolynomial time algorithm for subset sum. In: Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1073\u20131084 (2017)","DOI":"10.1137\/1.9781611974782.69"},{"key":"928_CR3","volume-title":"Introduction to Algorithms","author":"Thomas H Cormen","year":"2009","unstructured":"Cormen, Thomas H., Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford: Introduction to Algorithms, 3rd edn. The MIT Press, Cambridge (2009)","edition":"3"},{"issue":"1","key":"928_CR4","doi-asserted-by":"publisher","first-page":"14:1","DOI":"10.1145\/3293465","volume":"15","author":"Marek Cygan","year":"2019","unstructured":"Cygan, Marek, Mucha, Marcin, Wegrzycki, Karol, Wlodarczyk, Michal: On problems equivalent to (min, +)-convolution. ACM Trans. Algorithms 15(1), 14:1-14:25 (2019)","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"928_CR5","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1137\/0117039","volume":"17","author":"Ronald L Graham","year":"1969","unstructured":"Graham, Ronald L.: Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math. 17(2), 416\u2013429 (1969)","journal-title":"SIAM J. Appl. Math."},{"key":"928_CR6","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85\u2013103. Springer, Berlin (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"928_CR7","doi-asserted-by":"crossref","unstructured":"Koiliaris, K., Xu, C.: A faster pseudopolynomial time algorithm for subset sum. In: Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1062\u20131072 (2017)","DOI":"10.1137\/1.9781611974782.68"},{"key":"928_CR8","doi-asserted-by":"crossref","unstructured":"Kosaraju, S.R.: Efficient tree pattern matching. In: Proceedings of the 30th annual symposium on Foundations Of Computer Science (FOCS), pp. 178\u2013183 (1989)","DOI":"10.1109\/SFCS.1989.63475"},{"key":"928_CR9","unstructured":"K\u00fcnnemann, M., Paturi, R., Schneider, S.: On the fine-grained complexity of one-dimensional dynamic programming. In: Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP), pp. 21:1\u201321:15 (2017)"},{"issue":"1","key":"928_CR10","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1287\/mnsc.16.1.77","volume":"16","author":"Eugene L Lawler","year":"1969","unstructured":"Lawler, Eugene L., Moore, James M.: A functional equation and its application to resource allocation and sequencing problems. Manage. Sci. 16(1), 77\u201384 (1969)","journal-title":"Manage. Sci."},{"issue":"3","key":"928_CR11","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1006\/jsco.1994.1042","volume":"18","author":"Victor Y Pan","year":"1994","unstructured":"Pan, Victor Y.: Simple multivariate polynomial multiplication. J. Symb. Comput. 18(3), 183\u2013186 (1994)","journal-title":"J. Symb. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00928-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-00928-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00928-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,28]],"date-time":"2022-04-28T05:03:49Z","timestamp":1651122229000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-00928-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,27]]},"references-count":11,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,5]]}},"alternative-id":["928"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-00928-w","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2022,1,27]]},"assertion":[{"value":"15 December 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 January 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 January 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}