Pith.

Data Structures and Algorithms · arXiv:2210.07018 v3 · submitted 13 Oct 2022

Online matching with delays and stochastic arrival times

Mathieu Mari, Micha{l} Paw{l}owski, Runtian Ren, Piotr Sankowski

The paper says

“For such a problem, we show that the above lower bound can be improved by presenting two deterministic online algorithms, which, in expectation, are constant-competitive.”

from the abstract · picked out as the main claim by a classifier

Pith says

Pith has not reviewed this paper.

Get a Pith Review, $5

Reviews

Reviews by people

No person has reviewed this paper on Pith yet. A scientist listed on Pith can review it for a fee, and their review is published here whatever it concludes.

Request a human review

How Pith checks papers · The full audit of this paper

The paper

Abstract

This paper presents a new research direction for the Min-cost Perfect Matching with Delays (MPMD) - a problem introduced by Emek et al. (STOC'16). In the original version of this problem, we are given an n-point metric space, where requests arrive in an online fashion. The goal is to minimise the matching cost for an even number of requests. However, contrary to traditional online matching problems, a request does not have to be paired immediately at the time of its arrival. Instead, the decision of whether to match a request can be postponed for time t at a delay cost of t. For this reason, the goal of the MPMD is to minimise the overall sum of distance and delay costs. Interestingly, for adversarially generated requests, no online algorithm can achieve a competitive ratio better than O(logn/loglogn) (Ashlagi et al., APPROX/RANDOM'17). Here, we consider a stochastic version of the MPMD problem where the input requests follow a Poisson arrival process. For such a problem, we show that the above lower bound can be improved by presenting two deterministic online algorithms, which, in expectation, are constant-competitive. The first one is a simple greedy algorithm that matches any two requests once the sum of their delay costs exceeds their connection cost, i.e., the distance between them. The second algorithm builds on the tools used to analyse the first one in order to obtain even better performance guarantees. This result is rather surprising as the greedy approach for the adversarial model achieves a competitive ratio of Ω(mlog3/2 + ε), where m denotes the number of requests served (Azar et al., TOCS'20). Finally, we prove that it is possible to obtain similar results for the general case when the delay cost follows an arbitrary positive and non-decreasing function, as well as for the MPMD variant with penalties to clear pending requests.

The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. No sentence in this record was written by a model.

abstract compiled · 2026-09-23 · no language-model review

How the main claim is stated: asserted 1.00

What the abstract itself states, as probabilities: claims first 0.23 · states limitation 0.21 · human participants 0.02 · controlled comparison 0.14 · randomized assignment 0.02 · states quantitative result 0.95 · compares with prior results 0.97 · mentions code or data availability 0.02

The abstract, sentence by sentence

This table labels the abstract only (arXiv listing abstract v3). The number is the probability the classifier gave the label.

SentenceRoleThe authors' own workStates the main conclusionStrength
This paper presents a new research direction for the Min-cost Perfect Matching with Delays (MPMD) - a problem introduced by Emek et al. (STOC'16). contribution 0.68 0.67 0.04 asserted 0.99
In the original version of this problem, we are given an $n$-point metric space, where requests arrive in an online fashion. background 1.00 0.05 0.02 asserted 1.00
The goal is to minimise the matching cost for an even number of requests. background 1.00 0.05 0.02 asserted 1.00
However, contrary to traditional online matching problems, a request does not have to be paired immediately at the time of its arrival. background 1.00 0.06 0.02 asserted 0.99
Instead, the decision of whether to match a request can be postponed for time $t$ at a delay cost of $t$. background 1.00 0.06 0.02 asserted 0.97
For this reason, the goal of the MPMD is to minimise the overall sum of distance and delay costs. background 1.00 0.08 0.03 asserted 1.00
Interestingly, for adversarially generated requests, no online algorithm can achieve a competitive ratio better than $O(\log n/\log \log n)$ (Ashlagi et al., APPROX/RANDOM'17). background 0.94 0.04 0.03 asserted 1.00
Here, we consider a stochastic version of the MPMD problem where the input requests follow a Poisson arrival process. contribution 0.78 0.48 0.04 asserted 0.98
For such a problem, we show that the above lower bound can be improved by presenting two deterministic online algorithms, which, in expectation, are constant-competitive. result 0.87 0.96 0.84 asserted 1.00
The first one is a simple greedy algorithm that matches any two requests once the sum of their delay costs exceeds their connection cost, i.e., the distance between them. method 0.79 0.88 0.07 asserted 0.99
The second algorithm builds on the tools used to analyse the first one in order to obtain even better performance guarantees. contribution 0.50 0.88 0.06 asserted 0.97
This result is rather surprising as the greedy approach for the adversarial model achieves a competitive ratio of $\Omega(m^{\log \frac{3}{2}+\varepsilon})$, where $m$ denotes the number of requests served (Azar et al., TOCS'20). interpretation 0.62 0.07 0.10 asserted 1.00
Finally, we prove that it is possible to obtain similar results for the general case when the delay cost follows an arbitrary positive and non-decreasing function, as well as for the MPMD variant with penalties to clear pending requests. result 0.72 0.93 0.15 asserted 0.79

What kind of paper the classifier reports this is: theoretical result 0.86 · evidence from proof or derivation 1.00

What was examined, and what was not

Sources read

  • arXiv listing abstract v3

Not examined

  • full text
  • figures and tables
  • references and citing sentences
  • relations to other papers

Levels run

  • P abstract

Not run

  • S sections
  • T body sentences
  • C citations
  • R cross-paper relations

How the labels were made

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-09-23: 1 request, 9,671 input tokens.

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. This record as JSON

Cited by 4 Pith papers
How the literature uses it

What this paper does with the arXiv papers it cites

Each citing sentence is taken from the citing paper's LaTeX source and typed by Pith's classifier. A label appears at probability 0.8 or more (0.95 for support), a contest at 0.7 or more; the quoted words are the citing authors'. How each label was checked · JSON

What it cites · 2 sentences without a confident label

Cites as background 3 papers
  • Deryckere and Umboh [ref] studied online matching with set delay, where the delay cost at any given time is an arbitrary function of the set of pending requests.

    Online Matching with Set and Concave Delays · Introduction · 0.97

  • Kessel et al. [ref] studied the bipartite version of the problem and Bäumler et al. [ref] studied the special case to maximize the number of pairs produced.

    2206.10287 · Introduction · 0.85

  • Other classical online problems have been also considered under such delay setting, such as the online service problem [ref] , the multi-level aggregation problem [ref] , facility location [ref] , bin packing [ref] , set cover [ref] and many others [ref] .

    Online k-Way Matching with Delays and the H-Metric · Introduction · 1.00

Challenges and discussion

Know something about this paper? Leave a comment.

No comments yet.

Sign in to comment