1 Search Results for "Chen, Ryder"


Document
Track A: Algorithms, Complexity and Games
Online Weighted Cardinality Joint Replenishment Problem with Delay

Authors: Ryder Chen, Jahanvi Khatkar, and Seeun William Umboh

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)


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.

Cite as

Ryder Chen, Jahanvi Khatkar, and Seeun William Umboh. Online Weighted Cardinality Joint Replenishment Problem with Delay. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 40:1-40:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.40},
  URN =		{urn:nbn:de:0030-drops-163815},
  doi =		{10.4230/LIPIcs.ICALP.2022.40},
  annote =	{Keywords: Online Algorithms, Delay, Joint Replenishment Problem}
}
  • Refine by Author
  • 1 Chen, Ryder
  • 1 Khatkar, Jahanvi
  • 1 Umboh, Seeun William

  • Refine by Classification
  • 1 Theory of computation → Online algorithms

  • Refine by Keyword
  • 1 Delay
  • 1 Joint Replenishment Problem
  • 1 Online Algorithms

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail