{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T14:46:55Z","timestamp":1770994015747,"version":"3.50.1"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2022,5,16]],"date-time":"2022-05-16T00:00:00Z","timestamp":1652659200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,5,16]],"date-time":"2022-05-16T00:00:00Z","timestamp":1652659200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000001","name":"U.S. National Science Foundation","doi-asserted-by":"crossref","award":["CCF-1527032"],"award-info":[{"award-number":["CCF-1527032"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000001","name":"U. S. National Science Foundation","doi-asserted-by":"crossref","award":["CCF-1527032"],"award-info":[{"award-number":["CCF-1527032"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000001","name":"U. S. National Science Foundation","doi-asserted-by":"crossref","award":["CCF-1655442"],"award-info":[{"award-number":["CCF-1655442"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000001","name":"U. S. National Science Foundation","doi-asserted-by":"crossref","award":["CCF-1655442"],"award-info":[{"award-number":["CCF-1655442"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000006","name":"U. S. Office of Naval Research","doi-asserted-by":"crossref","award":["N00014-18-1-2099"],"award-info":[{"award-number":["N00014-18-1-2099"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000006","name":"U. S. Office of Naval Research","doi-asserted-by":"crossref","award":["N00014-18-1-2099"],"award-info":[{"award-number":["N00014-18-1-2099"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["024.002.003"],"award-info":[{"award-number":["024.002.003"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We introduce and study a class of optimization problems we call replenishment problems with fixed turnover times: a very natural model that has received little attention in the literature. Clients with capacity for storing a certain commodity are located at various places; at each client the commodity depletes within a certain time, the turnover time, which is constant but can vary between locations. Clients should never run empty. The natural feature that makes this problem interesting is that we may schedule a replenishment (well) before a client becomes empty, but then the next replenishment will be due earlier also. This added workload needs to be balanced against the cost of routing vehicles to do the replenishments. In this paper, we focus on the aspect of minimizing routing costs. However, the framework of recurring tasks, in which the next job of a task must be done within a fixed amount of time after the previous one is much more general and gives an adequate model for many practical situations. Note that our problem has an infinite time horizon. However, it can be fully characterized by a compact input, containing only the location of each client and a turnover time. This makes determining its computational complexity highly challenging and indeed it remains essentially unresolved. We study the problem for two objectives:<jats:sc>min<\/jats:sc>\u2013<jats:sc>avg<\/jats:sc>\u00a0 minimizes the average tour cost and<jats:sc>min<\/jats:sc>\u2013<jats:sc>max<\/jats:sc>\u00a0 minimizes the maximum tour cost over all days. For<jats:sc>min<\/jats:sc>\u2013<jats:sc>max<\/jats:sc>\u00a0 we derive a logarithmic factor approximation for the problem on general metrics and a 6-approximation for the problem on trees, for which we have a proof of NP-hardness. For<jats:sc>min<\/jats:sc>\u2013<jats:sc>avg<\/jats:sc>\u00a0 we present a logarithmic factor approximation on general metrics, a 2-approximation for trees, and a pseudopolynomial time algorithm for the line. Many intriguing problems remain open.<\/jats:p>","DOI":"10.1007\/s00453-022-00974-4","type":"journal-article","created":{"date-parts":[[2022,5,16]],"date-time":"2022-05-16T06:02:38Z","timestamp":1652680958000},"page":"2597-2621","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Approximation Algorithms for Replenishment Problems with Fixed Turnover Times"],"prefix":"10.1007","volume":"84","author":[{"given":"Thomas","family":"Bosman","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7724-8990","authenticated-orcid":false,"given":"Martijn","family":"van Ee","sequence":"additional","affiliation":[]},{"given":"Yang","family":"Jiao","sequence":"additional","affiliation":[]},{"given":"Alberto","family":"Marchetti-Spaccamela","sequence":"additional","affiliation":[]},{"given":"R.","family":"Ravi","sequence":"additional","affiliation":[]},{"given":"Leen","family":"Stougie","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,5,16]]},"reference":[{"key":"974_CR1","doi-asserted-by":"crossref","unstructured":"Baller, A.C., van Ee, M., Hoogeboom, M., Stougie, L.: On the complexity of inventory routing problems when routing is easy. Networks 75(2), 113\u2013123 (2019)","DOI":"10.1002\/net.21908"},{"key":"974_CR2","unstructured":"Baruah, S., Goossens, J.: Scheduling real-time tasks: algorithms and complexity. In: Handbook of Scheduling: Algorithms, Models, and Performance Analysis. CRC Press, Boca Raton (2003)"},{"key":"974_CR3","unstructured":"Baruah, S., Rosier, L., Tulchinsky, I., Varvel, D.: The complexity of periodic maintenance. In: Proceedings of the International Computer Symposium, pp. 315\u2013320 (1990)"},{"key":"974_CR4","series-title":"Leibniz International Proceedings in Informatics (LIPIcs)","doi-asserted-by":"publisher","first-page":"5:1","DOI":"10.4230\/LIPIcs.FUN.2021.5","volume-title":"10th International Conference on Fun with Algorithms (FUN 2021)","author":"D Bil\u00f2","year":"2020","unstructured":"Bil\u00f2, D., Gual\u00e0, L., Leucci, S., Proietti, G., Scornavacca, G.: Cutting bamboo down to size. In: Farach-Colton, M., Prencipe, G., Uehara, R. (eds.) 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), vol. 157, p. 5:1-5:18. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl (2020). https:\/\/doi.org\/10.4230\/LIPIcs.FUN.2021.5"},{"issue":"4","key":"974_CR5","doi-asserted-by":"publisher","first-page":"763","DOI":"10.1007\/s00453-011-9505-6","volume":"63","author":"V Bonifaci","year":"2012","unstructured":"Bonifaci, V., Marchetti-Spaccamela, A.: Feasibility analysis of sporadic real-time multiprocessor task systems. Algorithmica 63(4), 763\u2013780 (2012)","journal-title":"Algorithmica"},{"key":"974_CR6","unstructured":"Bosman, T.: Relax, round, reformulate: near-optimal algorithms for planning problems in network design and scheduling. Ph.D. thesis, Vrije Universiteit Amsterdam (2019)"},{"key":"974_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/978-3-319-77404-6_17","volume-title":"LATIN 2018: Theoretical Informatics","author":"T Bosman","year":"2018","unstructured":"Bosman, T., van Ee, M., Jiao, Y., Marchetti-Spaccamela, A., Ravi, R., Stougie, L.: Approximation algorithms for replenishment problems with fixed turnover times. In: Bender, M., Farach-Colton, M., Mosteiro, M.A. (eds.) LATIN 2018: Theoretical Informatics. Lecture Notes in Computer Science, vol. 10807, pp. 217\u2013230. Springer, New York (2018)"},{"issue":"3","key":"974_CR8","doi-asserted-by":"publisher","first-page":"386","DOI":"10.1016\/j.jcss.2007.06.015","volume":"74","author":"C Calabro","year":"2008","unstructured":"Calabro, C., Impagliazzo, R., Kabenets, V., Paturi, R.: The complexity of unique $$k$$-sat: An isolation lemma for $$k$$-cnfs. J. Comput. Syst. Sci. 74(3), 386\u2013393 (2008)","journal-title":"J. Comput. Syst. Sci."},{"issue":"6","key":"974_CR9","doi-asserted-by":"publisher","first-page":"755","DOI":"10.1109\/12.144627","volume":"41","author":"MY Chan","year":"1992","unstructured":"Chan, M.Y., Chin, F.Y.L.: General schedulers for the pinwheel problem based on double-integer reduction. IEEE Trans. Comput. 41(6), 755\u2013768 (1992)","journal-title":"IEEE Trans. Comput."},{"issue":"5","key":"974_CR10","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1007\/BF01187034","volume":"9","author":"MY Chan","year":"1993","unstructured":"Chan, M.Y., Chin, F.Y.L.: Schedulers for larger classes of pinwheel instances. Algorithmica 9(5), 425\u2013462 (1993)","journal-title":"Algorithmica"},{"key":"974_CR11","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1007\/978-3-319-73117-9_26","volume-title":"SOFSEM 2018: Theory and Practice of Computer Science","author":"H Chuangpishit","year":"2018","unstructured":"Chuangpishit, H., Czyzowicz, J., Gasieniec, L., Georgiou, K., Jurdzinski, T., Kranakis, E.: Patrolling a path connecting a set of points with unbalanced frequencies of visits. In: Tjoa, A.M., Bellatreche, L., Biffl, S., van Leeuwen, J., Wiedermann, J. (eds.) SOFSEM 2018: Theory and Practice of Computer Science, pp. 367\u2013380. Springer, Cham (2018)"},{"issue":"1","key":"974_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/trsc.2013.0472","volume":"48","author":"LC Coelho","year":"2013","unstructured":"Coelho, L.C., Cordeau, J.F., Laporte, G.: Thirty years of inventory routing. Transp. Sci. 48(1), 1\u201319 (2013)","journal-title":"Transp. Sci."},{"issue":"3","key":"974_CR13","doi-asserted-by":"publisher","first-page":"674","DOI":"10.1287\/opre.1110.0919","volume":"59","author":"S Coene","year":"2011","unstructured":"Coene, S., Spieksma, F.C.R., Woeginger, G.J.: Charlemagne\u2019s challenge: the periodic latency problem. Oper. Res. 59(3), 674\u2013683 (2011)","journal-title":"Oper. Res."},{"key":"974_CR14","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/978-3-030-48966-3_16","volume-title":"Combinatorial Algorithms","author":"P Damaschke","year":"2020","unstructured":"Damaschke, P.: Two robots patrolling on a line: integer version and approximability. In: Gasieniec, L., Klasing, R., Radzik, T. (eds.) Combinatorial Algorithms, pp. 211\u2013223. Springer, Cham (2020)"},{"issue":"4","key":"974_CR15","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1145\/2635812","volume":"10","author":"H Dell","year":"2014","unstructured":"Dell, H., Husfeldt, T., Marx, D., Taslaman, N., Wahl\u00e9n, M.: Exponential time complexity of the permanent and the tutte polynomial. ACM Trans. Algorithms 10(4), 211\u20132132 (2014)","journal-title":"ACM Trans. Algorithms"},{"key":"974_CR16","unstructured":"Della\u00a0Croce, F.: An enhanced pinwheel algorithm for the bamboo garden trimming problem. arXiv preprint arXiv:2003.12460 (2020)"},{"key":"974_CR17","doi-asserted-by":"crossref","unstructured":"Eisenbrand, F., H\u00e4hnle, N., Niemeier, M., Skutella, M., Verschae, J., Wiese, A.: Scheduling periodic tasks in a hard real-time environment. In: Proceedings of the 37th International Colloquium on Automata, Languages, and Programming, pp. 299\u2013311. Springer (2010)","DOI":"10.1007\/978-3-642-14165-2_26"},{"issue":"1","key":"974_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s11241-015-9225-0","volume":"52","author":"P Ekberg","year":"2016","unstructured":"Ekberg, P., Yi, W.: Schedulability analysis of a graph-based task model for mixed-criticality systems. Real-Time Syst. 52(1), 1\u201337 (2016). https:\/\/doi.org\/10.1007\/s11241-015-9225-0","journal-title":"Real-Time Syst."},{"issue":"3","key":"974_CR19","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1016\/j.jcss.2004.04.011","volume":"69","author":"J Fakcharoenphol","year":"2004","unstructured":"Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. Syst. Sci. 69(3), 485\u2013497 (2004)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"974_CR20","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1007\/s00453-002-0938-9","volume":"34","author":"PC Fishburn","year":"2002","unstructured":"Fishburn, P.C., Lagarias, J.C.: Pinwheel scheduling: achievable densities. Algorithmica 34(1), 14\u201338 (2002)","journal-title":"Algorithmica"},{"key":"974_CR21","doi-asserted-by":"crossref","unstructured":"Frederickson, G.N., Hecht, M.S., Kim, C.E.: Approximation algorithms for some routing problems. In: Proceedings of the 17th International Symposium on Foundations of Computer Science, pp. 216\u2013227 (1976)","DOI":"10.1109\/SFCS.1976.6"},{"issue":"4","key":"974_CR22","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1137\/0204035","volume":"4","author":"MR Garey","year":"1975","unstructured":"Garey, M.R., Johnson, D.S.: Complexity results for multiprocessor scheduling under resource constraints. SIAM J. Comput. 4(4), 397\u2013411 (1975)","journal-title":"SIAM J. Comput."},{"key":"974_CR23","doi-asserted-by":"crossref","unstructured":"Gasieniec, L., Klasing, R., Levcopoulos, C., Lingas, A., Min, J., Radzik, T.: Bamboo garden trimming problem. In: SOFSEM, pp. 229\u2013240. Springer (2017)","DOI":"10.1007\/978-3-319-51963-0_18"},{"key":"974_CR24","doi-asserted-by":"crossref","unstructured":"Holte, R., Mok, A., Rosier, L., Tulchinsky, I., Varvel, D.: The pinwheel: a real-time scheduling problem. In: Proceedings of the 22th Annual Hawaii International Conference on System Sciences, vol.\u00a02, pp. 693\u2013702 (1989)","DOI":"10.1109\/HICSS.1989.48075"},{"key":"974_CR25","unstructured":"Jacobs, T., Longo, S.: A new perspective on the windows scheduling problem. arXiv preprint arXiv:1410.7237 (2014)"},{"issue":"1","key":"974_CR26","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1006\/jagm.1995.1029","volume":"19","author":"P Klein","year":"1995","unstructured":"Klein, P., Ravi, R.: A nearly best-possible approximation algorithm for node-weighted steiner trees. J. Algorithms 19(1), 104\u2013115 (1995)","journal-title":"J. Algorithms"},{"issue":"1\u20135","key":"974_CR27","doi-asserted-by":"publisher","first-page":"657","DOI":"10.1016\/0165-6074(89)90128-2","volume":"27","author":"A Mok","year":"1989","unstructured":"Mok, A., Rosier, L., Tulchinksy, I., Varvel, D.: Algorithms and complexity of the periodic maintenance problem. Microprocess. Microprogram. 27(1\u20135), 657\u2013664 (1989)","journal-title":"Microprocess. Microprogram."},{"issue":"5","key":"974_CR28","doi-asserted-by":"publisher","first-page":"645","DOI":"10.1016\/j.orl.2021.07.001","volume":"49","author":"M van Ee","year":"2021","unstructured":"van Ee, M.: A 12\/7-approximation algorithm for the discrete bamboo garden trimming problem. Oper. Res. Lett. 49(5), 645\u2013649 (2021)","journal-title":"Oper. Res. Lett."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00974-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-00974-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00974-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,24]],"date-time":"2024-09-24T22:22:55Z","timestamp":1727216575000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-00974-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,16]]},"references-count":28,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2022,9]]}},"alternative-id":["974"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-00974-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,5,16]]},"assertion":[{"value":"27 December 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 April 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 May 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}