2026-07-24T06:30:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16381 2024-03-06T10:57:19Z ddc:004 open_access

Online Weighted Cardinality Joint Replenishment Problem with Delay Chen, Ryder Khatkar, Jahanvi Umboh, Seeun William Online Algorithms Delay Joint Replenishment Problem We study a generalization of the classic Online Joint Replenishment Problem (JRP) with Delays that we call the Online Weighted Cardinality JRP with Delays. The JRP is an extensively studied inventory management problem wherein requests for different item types arrive at various points in time. A request is served by ordering its corresponding item type. The cost of serving a set of requests depends on the item types ordered. Furthermore, each request incurs a delay penalty while it is left unserved. The objective is to minimise the total service and delay costs. In the Weighted Cardinality JRP, each item type has a positive weight and the cost of ordering is a non-decreasing, concave function of the total weight of the item types ordered. This problem was first considered in the offline setting by Cheung et al. (2015) but nothing is known in the online setting. Our main result is a deterministic, constant competitive algorithm for this problem. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ryder Chen and Jahanvi Khatkar and Seeun William Umboh 2022 Is Part Of LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2022.40 urn:nbn:de:0030-drops-163815 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.40 eng https://creativecommons.org/licenses/by/4.0/legalcode