License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2022.40
URN: urn:nbn:de:0030-drops-163815
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16381/
Go to the corresponding LIPIcs Volume Portal

Chen, Ryder ; Khatkar, Jahanvi ; Umboh, Seeun William

Online Weighted Cardinality Joint Replenishment Problem with Delay

pdf-format:
LIPIcs-ICALP-2022-40.pdf (0.7 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{chen_et_al:LIPIcs.ICALP.2022.40,
  author =	{Chen, Ryder and Khatkar, Jahanvi and Umboh, Seeun William},
  title =	{{Online Weighted Cardinality Joint Replenishment Problem with Delay}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{40:1--40:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16381},
  URN =		{urn:nbn:de:0030-drops-163815},
  doi =		{10.4230/LIPIcs.ICALP.2022.40},
  annote =	{Keywords: Online Algorithms, Delay, Joint Replenishment Problem}
}

Keywords: Online Algorithms, Delay, Joint Replenishment Problem
Collection: 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Issue Date: 2022
Date of publication: 28.06.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI