Online Matching with Size-Based and Convex Delays

Junhao Gan; Seeun William Umboh; Xiao Sun

arxiv: 2607.00536 · v1 · pith:NI6WAUGInew · submitted 2026-07-01 · 💻 cs.DS

Online Matching with Size-Based and Convex Delays

Junhao Gan , Xiao Sun , Seeun William Umboh This is my paper

Pith reviewed 2026-07-02 04:34 UTC · model grok-4.3

classification 💻 cs.DS

keywords online matchingcompetitive analysismetrical task systemsdelay functionssize-based delaysconvex delaysuniform metrics

0 comments

The pith

Size-based delays in online matching encode as a metrical task system on a 2^{n-1}-point metric, settling the deterministic competitive ratio up to constants, while polynomial convex delays with positive initial slope admit O(1)-competitive

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies online min-cost perfect matching where an algorithm may delay matches at a cost depending on either the count of unmatched requests or a convex function of waiting time. For size-based delay functions it constructs an encoding that turns the original problem on an n-point metric into a metrical task system on a metric with 2^{n-1} points, yielding competitive-ratio bounds that depend only on n rather than the total number of requests. For convex delay functions that are non-negative monotone polynomials with positive derivative at zero it gives a deterministic algorithm that remains constant-competitive on uniform metrics, in contrast to earlier Omega(n) lower bounds that required the derivative at zero to be zero. These two results together pin down the deterministic competitiveness of both delay models on uniform and general metrics up to constant factors.

Core claim

The central claim is that any MPMD-Size instance on an n-point metric reduces via a succinct encoding to an equivalent metrical task system on a 2^{n-1}-point metric, which immediately settles the deterministic competitive ratio up to constants; separately, when the convex delay is a non-negative monotone polynomial satisfying f'(0) greater than zero, an explicit deterministic algorithm achieves O(1) competitiveness on any uniform metric.

What carries the argument

The succinct encoding of an MPMD-Size instance on an n-point metric as a metrical task system on a 2^{n-1}-point metric, which preserves competitiveness.

If this is right

The deterministic competitive ratio for MPMD-Size is settled up to constant factors and depends only on the number of points n.
An O(1)-competitive deterministic algorithm exists for MPMD-Convex on uniform metrics whenever the polynomial delay has positive derivative at zero.
All bounds hold independently of the total number of arriving requests m.
The Omega(n) lower bound previously shown for convex delays does not apply to the subclass of polynomials with positive initial slope.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The exponential-size encoding may let existing metrical-task-system lower-bound techniques transfer directly to produce matching lower bounds.
Analogous state-compression encodings could be attempted for other online problems whose delay cost depends on the set of pending requests.
The sharp distinction created by whether f'(0) equals zero suggests that the local behavior of the delay function near the origin controls whether constant competitiveness is possible.
Extending the O(1) result from uniform metrics to general metrics for the same polynomial class would require new techniques beyond the encoding used for size-based delays.

Load-bearing premise

The delay functions must belong exactly to the studied classes: non-negative monotone functions of the number of unmatched requests for size-based delays, and non-negative monotone polynomials with positive derivative at zero for convex delays.

What would settle it

A concrete instance of a uniform metric with n greater than some constant together with a non-negative monotone polynomial delay f satisfying f'(0) greater than zero on which every deterministic algorithm incurs competitive ratio growing with n would falsify the O(1) claim.

read the original abstract

We study the online min-cost perfect matching with delay (MPMD) problem where $m$ requests arrive in a metric space of $n$ points. In MPMD, an algorithm can choose to match a request or to delay, and the objective is to minimise the sum of connection and delay costs. The connection cost of a match is the distance between the locations of two matched requests in the metric, and the increase of the delay cost is a function of the set of unmatched requests at every moment. In this paper, we study two different types of delay functions, size-based (MPMD-Size) and convex delays (MPMD-Convex). The study of MPMD-Size was initiated by Deryckere and Umboh (APPROX/RANDOM 2023) where the instantaneous delay increment is a non-negative monotone function of the number of unmatched requests. Our bounds are in terms of $n$, as opposed to Deryckere and Umboh's bounds that depend on $m$. Our results settle the deterministic competitive ratio (up to constants). At the heart of these results is a succinct encoding scheme of MPMD-Size on a given $n$-point metric as a metrical task system problem on a $2^{n-1}$-point metric. We also consider MPMD-Convex proposed by Liu et al. (ISAAC 2018) where the delay cost incurred by each request is a uniform convex delay function of the time difference between its arrival time and the moment that it is matched by the algorithm. They focused on delay functions $f$ that are unbounded, non-decreasing, continuous, and satisfy $f(0)=f'(0)=0$, and showed that the deterministic competitive ratio is $\Omega(n)$ for $n$-point uniform metrics. We show that, surprisingly, when $f$ is a non-negative, monotone polynomial with $f'(0)>0$, there is an $O(1)$-competitive deterministic algorithm for uniform metrics. Our result completes our understanding of MPMD-Convex on uniform metrics for a broad class of functions.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper settles the deterministic competitive ratio for MPMD-Size up to constants via an MTS reduction and gives the first O(1) bound for convex delays with f'(0)>0 on uniform metrics.

read the letter

The core advance here is closing the deterministic competitive ratio for MPMD-Size (up to constants) and showing an O(1) algorithm for a natural subclass of convex delays on uniform metrics. The size-based result comes from encoding the problem as a metrical task system on a 2^{n-1}-point space, which is a compact way to capture the unmatched set. That reduction lets them apply known MTS bounds directly. For the convex side, the key is the condition f'(0)>0 on monotone polynomials, which separates it from the earlier Omega(n) lower bound when the derivative is zero at the origin.

The reduction itself looks like the strongest technical piece. It improves on the m-dependent bounds from Deryckere and Umboh by working in terms of n, the number of points. The convex result is also clean: it completes the picture for uniform metrics across the two regimes of f. Both contributions sit squarely on top of the cited prior work without obvious circularity.

The main limitation visible from the abstract is that the MTS instance has exponentially many states. This settles the ratio but leaves open whether there is a polynomial-time algorithm that achieves it, or whether the result is purely existential for the competitive ratio. The O(1) convex algorithm is stated only for uniform metrics, so its behavior on general metrics is not addressed. No other load-bearing gaps jump out.

This is for people working on online algorithms and competitive analysis, especially those following matching with delays or metrical task systems. It addresses a stated open question with a concrete construction, so it deserves a serious referee. I would bring the full version to a reading group to check the details of the encoding and the convex construction.

Referee Report

0 major / 2 minor

Summary. The paper studies the online min-cost perfect matching with delay (MPMD) problem on n-point metrics. For size-based delays (MPMD-Size), where the instantaneous delay increment is a non-negative monotone function of the number of unmatched requests, it gives a succinct encoding that reduces the problem to a metrical task system (MTS) instance on a 2^{n-1}-point metric; applying known MTS bounds yields an O(n)-competitive deterministic algorithm (up to constants), settling the deterministic competitive ratio in terms of n. For convex delays (MPMD-Convex) on uniform metrics, when the delay function f is a non-negative monotone polynomial with f'(0)>0, it gives an O(1)-competitive deterministic algorithm, in contrast to the prior Ω(n) lower bound that held for functions with f'(0)=0.

Significance. If the results hold, the work settles the deterministic competitive ratio (up to constants) for MPMD-Size in terms of the metric size n rather than the number of requests m, via an explicit reduction to MTS whose state space size is 2^{n-1}. It also completes the picture for MPMD-Convex on uniform metrics across a broad natural class of delay functions. The reduction and the O(1) construction for polynomials with positive derivative at zero are the central technical contributions.

minor comments (2)

[Abstract] Abstract, paragraph on MPMD-Size: the claim that the results 'settle the deterministic competitive ratio (up to constants)' would be clearer if the exact dependence (e.g., O(n) or Θ(n)) were stated explicitly rather than left implicit from the MTS reduction.
[Introduction] The paper would benefit from a short table in the introduction that directly compares the new n-dependent bounds for MPMD-Size against the m-dependent bounds of Deryckere and Umboh (APPROX/RANDOM 2023).

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive review, detailed summary of our contributions, and recommendation to accept. No major comments were raised.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper's central claims rest on two explicit algorithmic contributions: (1) a new succinct encoding reducing MPMD-Size on an n-point metric to an MTS instance on a 2^{n-1}-point metric, from which known MTS bounds yield the O(n) deterministic ratio (up to constants); and (2) a new O(1)-competitive deterministic algorithm for MPMD-Convex on uniform metrics that exploits the condition f'(0)>0 for the specified polynomial class. Both are presented as self-contained constructions. The citation to Deryckere and Umboh (co-author overlap) is used only to contextualize prior m-dependent bounds; it is not load-bearing for the new n-dependent results or the convex-case algorithm. No equations reduce predictions to fitted parameters, no ansatzes are smuggled via self-citation, and no uniqueness theorems from the authors' prior work are invoked to force the current choices. The derivation chain is therefore independent of its inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 3 axioms · 0 invented entities

Results rest on standard metric-space axioms and the precise functional forms of the two delay classes; no free parameters or invented entities are introduced.

axioms (3)

domain assumption The input is a metric space on n points.
Stated in the problem definition for both MPMD variants.
domain assumption Size-based delay increment is a non-negative monotone function of the number of unmatched requests.
Definition of MPMD-Size.
domain assumption Convex delay is a non-negative monotone polynomial with f'(0) > 0.
Definition of the subclass of MPMD-Convex for which the O(1) result holds.

pith-pipeline@v0.9.1-grok · 5932 in / 1461 out tokens · 25481 ms · 2026-07-02T04:34:59.413227+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

15 extracted references · 14 canonical work pages · 1 internal anchor

[1]

Min-cost bipartite perfect match- ing with delays

1 Itai Ashlagi, Yossi Azar, Moses Charikar, Ashish Chiplunkar, Ofir Geri, Haim Kaplan, Rahul Makhijani, Yuyi Wang, and Roger Wattenhofer. Min-cost bipartite perfect match- ing with delays. In Klaus Jansen, José D. P. Rolim, David Williamson, and Santosh S. Vempala, editors,Approximation, Randomization, and Combinatorial Optimization. Al- gorithms and Tech...

2017
[2]

2 Yossi Azar, Ashish Chiplunkar, and Haim Kaplan

URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.1, doi:10.4230/ LIPICS.APPROX-RANDOM.2017.1. 2 Yossi Azar, Ashish Chiplunkar, and Haim Kaplan. Polylogarithmic bounds on the com- petitiveness of min-cost perfect matching with delays. In Philip N. Klein, editor,Proceed- ings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ...

work page doi:10.4230/lipics.approx-random.2017.1 2017
[3]

3 Yossi Azar, Ashish Chiplunkar, Shay Kutten, and Noam Touitou

doi:10.1137/1.9781611974782.67. 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, Pisa, Italy (Virtual Conference), September 7-9, 2020, volume 173 ofLIPIcs, pages 8:1–...

work page doi:10.1137/1.9781611974782.67 2020
[4]

URL:https://doi.org/10.4230/LIPIcs.ESA.2020.8, doi:10.4230/LIPICS.ESA.2020.8. J. Gan, X. Sun, S. W. Umboh 27 4 Yossi Azar and Amit Jacob Fanani. Deterministic min-cost matching with delays.Theory Comput. Syst., 64(4):572–592,

work page doi:10.4230/lipics.esa.2020.8 2020
[5]

5 Yossi Azar, Runtian Ren, and Danny Vainstein

URL:https://doi.org/10.1007/s00224-019-09963-7, doi:10.1007/S00224-019-09963-7. 5 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.doi:10.1...

work page doi:10.1007/s00224-019-09963-7 2021
[6]

7 Sujoy Bhore, Michał Pawłowski, and Seeun William Umboh

doi: 10.1145/2783434. 7 Sujoy Bhore, Michał Pawłowski, and Seeun William Umboh. Online tcp acknowledgment under general delays. InApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM

work page doi:10.1145/2783434
[7]

Online TCP Acknowledgment under General Delays

To appear. Full version available as arXiv:2604.13428 [cs.DS]. 8 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, W AOA 2018, Helsinki, Finland, August 2...

work page internal anchor Pith review Pith/arXiv arXiv doi:10.1007/978-3-030-04693-4 2018
[8]

11 Sébastien Bubeck, Christian Coester, and Yuval Rabani

doi:10.1145/28395.28435. 11 Sébastien Bubeck, Christian Coester, and Yuval Rabani. The randomized k-server conjecture is false! In Barna Saha and Rocco A. Servedio, editors,Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 581–594. ACM, 2023.doi:10.1145/3564246.3585132. 12 Sébastien B...

work page doi:10.1145/28395.28435 2023
[9]

13 Ryder Chen, Jahanvi Khatkar, and Seeun William Umboh

doi:10.1137/19M1237879. 13 Ryder Chen, Jahanvi Khatkar, and Seeun William Umboh. Online weighted cardinality joint replenishment problem with delay. In Mikolaj Bojanczyk, Emanuela Merelli, and David P. Woodruff, editors,49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, Paris, France, July 4-8, 2022, volume 229 ofLIPIcs, pa...

work page doi:10.1137/19m1237879 2022
[10]

ICALP.2022.40,doi:10.4230/LIPICS.ICALP.2022.40

URL:https://doi.org/10.4230/LIPIcs. ICALP.2022.40,doi:10.4230/LIPICS.ICALP.2022.40. 14 Lindsey Deryckere and Seeun William Umboh. Online matching with set and concave delays. In Nicole Megow and Adam D. Smith, editors,Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2023, Atlanta, Georgia, USA, Septemb...

work page doi:10.4230/lipics 2022
[11]

2023.17,doi:10.4230/LIPICS.APPROX/RANDOM.2023.17

URL: https://doi.org/10.4230/LIPIcs.APPROX/RANDOM. 2023.17,doi:10.4230/LIPICS.APPROX/RANDOM.2023.17. 15 Marc Dufay and Roger Wattenhofer. A deterministic polylogarithmic competitive algorithm for matching with delays. In Kasper Green Larsen and Barna Saha, editors,Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, Vancouv...

work page doi:10.4230/lipics.approx/random 2023
[12]

DISOPT.2021.100647

URL: https://doi.org/10.1016/j.disopt.2021.100647, doi:10.1016/J. DISOPT.2021.100647. 18 Tomer Ezra, Stefano Leonardi, Michal Pawlowski, Matteo Russo, and Seeun William Umboh. Universal optimization for non-clairvoyant subadditive joint replenishment. In Amit Kumar and Noga Ron-Zewi, editors,Approximation, Randomization, and Combinatorial Optimization. Al...

work page doi:10.1016/j.disopt.2021.100647 2021
[13]

19 Ngoc Mai Le, Seeun William Umboh, and Ningyuan Xie

URL: https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.12, doi: 10.4230/LIPICS.APPROX/RANDOM.2024.12. 19 Ngoc Mai Le, Seeun William Umboh, and Ningyuan Xie. The power of clairvoyance for multi-level aggregation and set cover with delay. In Nikhil Bansal and Viswanath Nagarajan, editors,Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SOD...

work page doi:10.4230/lipics.approx/random.2024.12 2024
[14]

20 Xingwu Liu, Zhida Pan, Yuyi Wang, and Roger Wattenhofer

URL: https: //doi.org/10.1137/1.9781611977554.ch59,doi:10.1137/1.9781611977554.CH59. 20 Xingwu Liu, Zhida Pan, Yuyi Wang, and Roger Wattenhofer. Impatient online matching. In Wen-Lian Hsu, Der-Tsai Lee, and Chung-Shou Liao, editors,29th International Symposium on Algorithms and Computation, ISAAC 2018, December 16-19, 2018, Jiaoxi, Yilan, Taiwan, volume 1...

work page doi:10.1137/1.9781611977554.ch59 2018
[15]

URL:https://doi.org/10.4230/LIPIcs.ISAAC.2018.62, doi:10.4230/LIPICS.ISAAC. 2018.62. J. Gan, X. Sun, S. W. Umboh 29 A Proofs for Section 2 (Preliminaries) ▶Lemma 2.1.Given any online algorithmAfor MTS, there is an online mechanism that transformsAto a lazy algorithm without increasing the cost. Proof. Suppose that the state ofA to process requestρt is st ...

work page doi:10.4230/lipics.isaac.2018.62 2018

[1] [1]

Min-cost bipartite perfect match- ing with delays

1 Itai Ashlagi, Yossi Azar, Moses Charikar, Ashish Chiplunkar, Ofir Geri, Haim Kaplan, Rahul Makhijani, Yuyi Wang, and Roger Wattenhofer. Min-cost bipartite perfect match- ing with delays. In Klaus Jansen, José D. P. Rolim, David Williamson, and Santosh S. Vempala, editors,Approximation, Randomization, and Combinatorial Optimization. Al- gorithms and Tech...

2017

[2] [2]

2 Yossi Azar, Ashish Chiplunkar, and Haim Kaplan

URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.1, doi:10.4230/ LIPICS.APPROX-RANDOM.2017.1. 2 Yossi Azar, Ashish Chiplunkar, and Haim Kaplan. Polylogarithmic bounds on the com- petitiveness of min-cost perfect matching with delays. In Philip N. Klein, editor,Proceed- ings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ...

work page doi:10.4230/lipics.approx-random.2017.1 2017

[3] [3]

3 Yossi Azar, Ashish Chiplunkar, Shay Kutten, and Noam Touitou

doi:10.1137/1.9781611974782.67. 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, Pisa, Italy (Virtual Conference), September 7-9, 2020, volume 173 ofLIPIcs, pages 8:1–...

work page doi:10.1137/1.9781611974782.67 2020

[4] [4]

URL:https://doi.org/10.4230/LIPIcs.ESA.2020.8, doi:10.4230/LIPICS.ESA.2020.8. J. Gan, X. Sun, S. W. Umboh 27 4 Yossi Azar and Amit Jacob Fanani. Deterministic min-cost matching with delays.Theory Comput. Syst., 64(4):572–592,

work page doi:10.4230/lipics.esa.2020.8 2020

[5] [5]

5 Yossi Azar, Runtian Ren, and Danny Vainstein

URL:https://doi.org/10.1007/s00224-019-09963-7, doi:10.1007/S00224-019-09963-7. 5 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.doi:10.1...

work page doi:10.1007/s00224-019-09963-7 2021

[6] [6]

7 Sujoy Bhore, Michał Pawłowski, and Seeun William Umboh

doi: 10.1145/2783434. 7 Sujoy Bhore, Michał Pawłowski, and Seeun William Umboh. Online tcp acknowledgment under general delays. InApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM

work page doi:10.1145/2783434

[7] [7]

Online TCP Acknowledgment under General Delays

To appear. Full version available as arXiv:2604.13428 [cs.DS]. 8 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, W AOA 2018, Helsinki, Finland, August 2...

work page internal anchor Pith review Pith/arXiv arXiv doi:10.1007/978-3-030-04693-4 2018

[8] [8]

11 Sébastien Bubeck, Christian Coester, and Yuval Rabani

doi:10.1145/28395.28435. 11 Sébastien Bubeck, Christian Coester, and Yuval Rabani. The randomized k-server conjecture is false! In Barna Saha and Rocco A. Servedio, editors,Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 581–594. ACM, 2023.doi:10.1145/3564246.3585132. 12 Sébastien B...

work page doi:10.1145/28395.28435 2023

[9] [9]

13 Ryder Chen, Jahanvi Khatkar, and Seeun William Umboh

doi:10.1137/19M1237879. 13 Ryder Chen, Jahanvi Khatkar, and Seeun William Umboh. Online weighted cardinality joint replenishment problem with delay. In Mikolaj Bojanczyk, Emanuela Merelli, and David P. Woodruff, editors,49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, Paris, France, July 4-8, 2022, volume 229 ofLIPIcs, pa...

work page doi:10.1137/19m1237879 2022

[10] [10]

ICALP.2022.40,doi:10.4230/LIPICS.ICALP.2022.40

URL:https://doi.org/10.4230/LIPIcs. ICALP.2022.40,doi:10.4230/LIPICS.ICALP.2022.40. 14 Lindsey Deryckere and Seeun William Umboh. Online matching with set and concave delays. In Nicole Megow and Adam D. Smith, editors,Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2023, Atlanta, Georgia, USA, Septemb...

work page doi:10.4230/lipics 2022

[11] [11]

2023.17,doi:10.4230/LIPICS.APPROX/RANDOM.2023.17

URL: https://doi.org/10.4230/LIPIcs.APPROX/RANDOM. 2023.17,doi:10.4230/LIPICS.APPROX/RANDOM.2023.17. 15 Marc Dufay and Roger Wattenhofer. A deterministic polylogarithmic competitive algorithm for matching with delays. In Kasper Green Larsen and Barna Saha, editors,Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, Vancouv...

work page doi:10.4230/lipics.approx/random 2023

[12] [12]

DISOPT.2021.100647

URL: https://doi.org/10.1016/j.disopt.2021.100647, doi:10.1016/J. DISOPT.2021.100647. 18 Tomer Ezra, Stefano Leonardi, Michal Pawlowski, Matteo Russo, and Seeun William Umboh. Universal optimization for non-clairvoyant subadditive joint replenishment. In Amit Kumar and Noga Ron-Zewi, editors,Approximation, Randomization, and Combinatorial Optimization. Al...

work page doi:10.1016/j.disopt.2021.100647 2021

[13] [13]

19 Ngoc Mai Le, Seeun William Umboh, and Ningyuan Xie

URL: https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.12, doi: 10.4230/LIPICS.APPROX/RANDOM.2024.12. 19 Ngoc Mai Le, Seeun William Umboh, and Ningyuan Xie. The power of clairvoyance for multi-level aggregation and set cover with delay. In Nikhil Bansal and Viswanath Nagarajan, editors,Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SOD...

work page doi:10.4230/lipics.approx/random.2024.12 2024

[14] [14]

20 Xingwu Liu, Zhida Pan, Yuyi Wang, and Roger Wattenhofer

URL: https: //doi.org/10.1137/1.9781611977554.ch59,doi:10.1137/1.9781611977554.CH59. 20 Xingwu Liu, Zhida Pan, Yuyi Wang, and Roger Wattenhofer. Impatient online matching. In Wen-Lian Hsu, Der-Tsai Lee, and Chung-Shou Liao, editors,29th International Symposium on Algorithms and Computation, ISAAC 2018, December 16-19, 2018, Jiaoxi, Yilan, Taiwan, volume 1...

work page doi:10.1137/1.9781611977554.ch59 2018

[15] [15]

URL:https://doi.org/10.4230/LIPIcs.ISAAC.2018.62, doi:10.4230/LIPICS.ISAAC. 2018.62. J. Gan, X. Sun, S. W. Umboh 29 A Proofs for Section 2 (Preliminaries) ▶Lemma 2.1.Given any online algorithmAfor MTS, there is an online mechanism that transformsAto a lazy algorithm without increasing the cost. Proof. Suppose that the state ofA to process requestρt is st ...

work page doi:10.4230/lipics.isaac.2018.62 2018