Document Open Access Logo

Online Weighted Cardinality Joint Replenishment Problem with Delay

Authors Ryder Chen, Jahanvi Khatkar, Seeun William Umboh

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.40.pdf
  • Filesize: 0.74 MB
  • 18 pages

Document Identifiers

Author Details

Ryder Chen
  • The University of Sydney, Australia
Jahanvi Khatkar
  • The University of Sydney, Australia
Seeun William Umboh
  • The University of Sydney, Australia

Cite As Get BibTex

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) https://doi.org/10.4230/LIPIcs.ICALP.2022.40

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Online algorithms
Keywords
  • Online Algorithms
  • Delay
  • Joint Replenishment Problem

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Itai Ashlagi, Yossi Azar, Moses Charikar, Ashish Chiplunkar, Ofir Geri, Haim Kaplan, Rahul Makhijani, Yuyi Wang, and Roger Wattenhofer. Min-cost bipartite perfect matching with delays. In Klaus Jansen, José D. P. Rolim, David Williamson, and Santosh S. Vempala, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2017, August 16-18, 2017, Berkeley, CA, USA, volume 81 of LIPIcs, pages 1:1-1:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.1.
  2. Baruch Awerbuch, Yossi Azar, and Yair Bartal. On-line generalized steiner problem. Theor. Comput. Sci., 324(2-3):313-324, 2004. URL: https://doi.org/10.1016/j.tcs.2004.05.021.
  3. Yossi Azar, Ashish Chiplunkar, Shay Kutten, and Noam Touitou. Set cover with delay - clairvoyance is not required. In Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders, editors, 28th Annual European Symposium on Algorithms, ESA 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference), volume 173 of LIPIcs, pages 8:1-8:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ESA.2020.8.
  4. Yossi Azar and Amit Jacob Fanani. Deterministic min-cost matching with delays. Theory Comput. Syst., 64(4):572-592, 2020. URL: https://doi.org/10.1007/s00224-019-09963-7.
  5. Yossi Azar, Arun Ganesh, Rong Ge, and Debmalya Panigrahi. Online service with delay. ACM Trans. Algorithms, 17(3):23:1-23:31, 2021. URL: https://doi.org/10.1145/3459925.
  6. Yossi Azar, Runtian Ren, and Danny Vainstein. The min-cost matching with concave delays problem. In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 301-320. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976465.20.
  7. Yossi Azar and Noam Touitou. General framework for metric optimization problems with delay or with deadlines. In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 60-71. IEEE Computer Society, 2019. URL: https://doi.org/10.1109/FOCS.2019.00013.
  8. Yossi Azar and Noam Touitou. Beyond tree embeddings - a deterministic framework for network design with deadlines or delay. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 1368-1379. IEEE, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00129.
  9. Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukáš Folwarczný, Lukasz Jez, Jiri Sgall, Nguyen Kim Thang, and Pavel Veselý. Online algorithms for multi-level aggregation. In Piotr Sankowski and Christos D. Zaroliagis, editors, 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark, volume 57 of LIPIcs, pages 12:1-12:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.ESA.2016.12.
  10. Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Lukasz Jez, Dorian Nogneng, and Jirí Sgall. Better approximation bounds for the joint replenishment problem. In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 42-54. SIAM, 2014. URL: https://doi.org/10.1137/1.9781611973402.4.
  11. Marcin Bienkowski, Artur Kraska, Hsiang-Hsuan Liu, and Pawel Schmidt. A primal-dual online deterministic algorithm for matching with delays. In Leah Epstein and Thomas Erlebach, editors, Approximation and Online Algorithms - 16th International Workshop, WAOA 2018, Helsinki, Finland, August 23-24, 2018, Revised Selected Papers, volume 11312 of Lecture Notes in Computer Science, pages 51-68. Springer, 2018. URL: https://doi.org/10.1007/978-3-030-04693-4_4.
  12. Marcin Bienkowski, Artur Kraska, and Pawel Schmidt. A match in time saves nine: Deterministic online matching with delays. In Roberto Solis-Oba and Rudolf Fleischer, editors, Approximation and Online Algorithms - 15th International Workshop, WAOA 2017, Vienna, Austria, September 7-8, 2017, Revised Selected Papers, volume 10787 of Lecture Notes in Computer Science, pages 132-146. Springer, 2017. URL: https://doi.org/10.1007/978-3-319-89441-6_11.
  13. Marcin Bienkowski, Artur Kraska, and Pawel Schmidt. Online service with delay on a line. In Zvi Lotker and Boaz Patt-Shamir, editors, Structural Information and Communication Complexity - 25th International Colloquium, SIROCCO 2018, Ma'ale HaHamisha, Israel, June 18-21, 2018, Revised Selected Papers, volume 11085 of Lecture Notes in Computer Science, pages 237-248. Springer, 2018. URL: https://doi.org/10.1007/978-3-030-01325-7_22.
  14. Niv Buchbinder, Moran Feldman, Joseph (Seffi) Naor, and Ohad Talmon. O(depth)-competitive algorithm for online multi-level aggregation. In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 1235-1244. SIAM, 2017. URL: https://doi.org/10.1137/1.9781611974782.80.
  15. Niv Buchbinder, Tracy Kimbrel, Retsef Levi, Konstantin Makarychev, and Maxim Sviridenko. Online Make-to-Order Joint Replenishment Model: Primal-Dual Competitive Algorithms. Oper. Res., 61(4):1014-1029, 2013. URL: https://doi.org/10.1287/opre.2013.1188.
  16. Rodrigo A. Carrasco, Kirk Pruhs, Cliff Stein, and José Verschae. The online set aggregation problem. In Michael A. Bender, Martin Farach-Colton, and Miguel A. Mosteiro, editors, LATIN 2018: Theoretical Informatics - 13th Latin American Symposium, Buenos Aires, Argentina, April 16-19, 2018, Proceedings, volume 10807 of Lecture Notes in Computer Science, pages 245-259. Springer, 2018. URL: https://doi.org/10.1007/978-3-319-77404-6_19.
  17. Sin-Shuen Cheung. The submodular facility location problem and the submodular joint replenishment problem. In Evripidis Bampis and Ola Svensson, editors, Approximation and Online Algorithms - 12th International Workshop, WAOA 2014, Wrocław, Poland, September 11-12, 2014, Revised Selected Papers, volume 8952 of Lecture Notes in Computer Science, pages 71-82. Springer, 2014. URL: https://doi.org/10.1007/978-3-319-18263-6_7.
  18. Nico P. Dellaert and M. Teresa Melo. Heuristic procedures for a stochastic lot-sizing problem in make-to-order manufacturing. Ann. Oper. Res., 59(1):227-258, 1995. URL: https://doi.org/10.1007/BF02031749.
  19. Yuval Emek, Shay Kutten, and Roger Wattenhofer. Online matching: haste makes waste! In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 333-344. ACM, 2016. URL: https://doi.org/10.1145/2897518.2897557.
  20. Yuval Emek, Yaacov Shapiro, and Yuyi Wang. Minimum cost perfect matching with delays for two sources. Theor. Comput. Sci., 754:122-129, 2019. URL: https://doi.org/10.1016/j.tcs.2018.07.004.
  21. Naveen Garg, Rohit Khandekar, Goran Konjevod, R. Ravi, F. Sibel Salman, and Amitabh Sinha II. On the integrality gap of a natural formulation of the single-sink buy-at-bulk network design problem. In Integer Programming and Combinatorial Optimization, 8th International IPCO Conference, Utrecht, The Netherlands, June 13-15, 2001, Proceedings, pages 170-184, 2001. URL: https://doi.org/10.1007/3-540-45535-3_14.
  22. Fabrizio Grandoni and Giuseppe F. Italiano. Improved approximation for single-sink buy-at-bulk. In Algorithms and Computation, 17th International Symposium, ISAAC 2006, Kolkata, India, December 18-20, 2006, Proceedings, pages 111-120, 2006. URL: https://doi.org/10.1007/11940128_13.
  23. Sudipto Guha, Adam Meyerson, and Kamesh Munagala. A constant factor approximation for the single sink edge installation problem. SIAM J. Comput., 38(6):2426-2442, 2009. URL: https://doi.org/10.1137/050643635.
  24. Anupam Gupta, Amit Kumar, and Debmalya Panigrahi. Caching with time windows. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 1125-1138. ACM, 2020. URL: https://doi.org/10.1145/3357713.3384277.
  25. Anupam Gupta, Amit Kumar, and Tim Roughgarden. Simpler and better approximation algorithms for network design. In 35th STOC, pages 365-372, 2003. Google Scholar
  26. Anupam Gupta, R. Ravi, Kunal Talwar, and Seeun William Umboh. LAST but not least: Online spanners for buy-at-bulk. In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 589-599. SIAM, 2017. URL: https://doi.org/10.1137/1.9781611974782.38.
  27. Raja Jothi and Balaji Raghavachari. Improved approximation algorithms for the single-sink buy-at-bulk network design problems. J. Discrete Algorithms, 7(2):249-255, 2009. URL: https://doi.org/10.1016/j.jda.2008.12.003.
  28. F. Sibel Salman, Joseph Cheriyan, R. Ravi, and S. Subramanian. Buy-at-bulk network design: Approximating the single-sink edge installation problem. In Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 5-7 January 1997, New Orleans, Louisiana., pages 619-628, 1997. URL: http://dl.acm.org/citation.cfm?id=314161.314397.
  29. Kunal Talwar. The single-sink buy-at-bulk LP has constant integrality gap. In Integer Programming and Combinatorial Optimization, 9th International IPCO Conference, Cambridge, MA, USA, May 27-29, 2002, Proceedings, pages 475-486, 2002. URL: http://link.springer.de/link/service/series/0558/bibs/2337/23370475.htm, URL: https://doi.org/10.1007/3-540-47867-1_33.
  30. Noam Touitou. Nearly-tight lower bounds for set cover and network design with deadlines/delay. In Hee-Kap Ahn and Kunihiko Sadakane, editors, 32nd International Symposium on Algorithms and Computation, ISAAC 2021, December 6-8, 2021, Fukuoka, Japan, volume 212 of LIPIcs, pages 53:1-53:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2021.53.
  31. Seeun Umboh. Online network design algorithms via hierarchical decompositions. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 1373-1387, 2015. URL: https://doi.org/10.1137/1.9781611973730.91.
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact