DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.77

Learning-Augmented Online Algorithms for Nonclairvoyant Joint Replenishment Problem with Deadlines

Authors: Michael Dinitz, Jeremy Fineman, and Seeun William Umboh

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract

This paper considers using predictions in the context of the online Joint Replenishment Problem with Deadlines (JRP-D). Prior work includes asymptotically optimal competitive ratios of O(1) for the clairvoyant setting and O(√n) of the nonclairvoyant setting, where n is the number of items. The goal of this paper is to significantly reduce the competitive ratio for the nonclairvoyant case by leveraging predictions: when a request arrives, the true deadline of the request is not revealed, but the algorithm is given a predicted deadline. The main result is an algorithm whose competitive ratio is O(min(η^{1/3} log^{2/3}(n), √η, √n)), where n is the number of item types and η ≤ n² quantifies how flawed the predictions are in terms of the number of "instantaneous item inversions." Thus, the algorithm is robust, i.e., it is never worse than the nonclairvoyant solution, and it is consistent, i.e., if the predictions exhibit no inversions, then the algorithm behaves similarly to the clairvoyant algorithm. Moreover, if the error is not too large, specifically η < o(n^{3/2}/log²(n)), then the algorithm obtains an asymptotically better competitive ratio than the nonclairvoyant algorithm. We also show that all deterministic algorithms falling in a certain reasonable class of algorithms have a competitive ratio of Ω(η^{1/3}), so this algorithm is nearly the best possible with respect to this error metric.

Cite as

Michael Dinitz, Jeremy Fineman, and Seeun William Umboh. Learning-Augmented Online Algorithms for Nonclairvoyant Joint Replenishment Problem with Deadlines. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 77:1-77:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{dinitz_et_al:LIPIcs.ICALP.2026.77,
  author =	{Dinitz, Michael and Fineman, Jeremy and Umboh, Seeun William},
  title =	{{Learning-Augmented Online Algorithms for Nonclairvoyant Joint Replenishment Problem with Deadlines}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{77:1--77:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.77},
  URN =		{urn:nbn:de:0030-drops-264664},
  doi =		{10.4230/LIPIcs.ICALP.2026.77},
  annote =	{Keywords: Online algorithms, Joint Replenishment, Algorithms with Predictions}
}

Document

DOI: 10.4230/LIPIcs.DISC.2022.18

Smoothed Analysis of Information Spreading in Dynamic Networks

Authors: Michael Dinitz, Jeremy Fineman, Seth Gilbert, and Calvin Newport

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract

The best known solutions for k-message broadcast in dynamic networks of size n require Ω(nk) rounds. In this paper, we see if these bounds can be improved by smoothed analysis. To do so, we study perhaps the most natural randomized algorithm for disseminating tokens in this setting: at every time step, choose a token to broadcast randomly from the set of tokens you know. We show that with even a small amount of smoothing (i.e., one random edge added per round), this natural strategy solves k-message broadcast in Õ(n+k³) rounds, with high probability, beating the best known bounds for k = o(√n) and matching the Ω(n+k) lower bound for static networks for k = O(n^{1/3}) (ignoring logarithmic factors). In fact, the main result we show is even stronger and more general: given 𝓁-smoothing (i.e., 𝓁 random edges added per round), this simple strategy terminates in O(kn^{2/3}log^{1/3}(n)𝓁^{-1/3}) rounds. We then prove this analysis close to tight with an almost-matching lower bound. To better understand the impact of smoothing on information spreading, we next turn our attention to static networks, proving a tight bound of Õ(k√n) rounds to solve k-message broadcast, which is better than what our strategy can achieve in the dynamic setting. This confirms the intuition that although smoothed analysis reduces the difficulties induced by changing graph structures, it does not eliminate them altogether. Finally, we apply tools developed to support our smoothed analysis to prove an optimal result for k-message broadcast in so-called well-mixed networks in the absence of smoothing. By comparing this result to an existing lower bound for well-mixed networks, we establish a formal separation between oblivious and strongly adaptive adversaries with respect to well-mixed token spreading, partially resolving an open question on the impact of adversary strength on the k-message broadcast problem.

Cite as

Michael Dinitz, Jeremy Fineman, Seth Gilbert, and Calvin Newport. Smoothed Analysis of Information Spreading in Dynamic Networks. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 18:1-18:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dinitz_et_al:LIPIcs.DISC.2022.18,
  author =	{Dinitz, Michael and Fineman, Jeremy and Gilbert, Seth and Newport, Calvin},
  title =	{{Smoothed Analysis of Information Spreading in Dynamic Networks}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{18:1--18:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.18},
  URN =		{urn:nbn:de:0030-drops-172094},
  doi =		{10.4230/LIPIcs.DISC.2022.18},
  annote =	{Keywords: Smoothed Analysis, Dynamic networks, Gossip}
}

Search Results

Documents authored by Fineman, Jeremy

Learning-Augmented Online Algorithms for Nonclairvoyant Joint Replenishment Problem with Deadlines

Abstract

Cite as

Smoothed Analysis of Information Spreading in Dynamic Networks

Abstract

Cite as

Thanks for your feedback!

Could not send message