CS Paper Radar

A General Framework for Matching with Delays

Sara Ahmadian, Shuchi Chawla, Ravi Kumar, Manish Purohit, Shirley Zhang

cs.DS ·submitted 2026-10-15 05:30 UTC · v1
theory

Abstract

We present a simple deterministic $O(\log n)$-competitive algorithm for the online minimum-cost perfect matching with delays (MPMD) problem on arbitrary, unknown metric spaces, where $n$ is the (unknown) number of requests. This improves upon the recent $O(\log^5 n)$-competitive algorithm of Dufay and Wattenhofer (SODA 2026) and nearly matches the $Ω(\log n / \log \log n)$ randomized lower bound of Ashlagi et al. (APPROX 2017). Our algorithmic framework rests on two ingredients: an online moat-growing process that grows active dual variables at a deliberately slowed constant rate $α< 1$ to control temporal asymmetry, and a delayed eligibility rule that matches requests in the same dual component only after their waiting time is proportional to their time-expanded distance. The framework extends naturally to arbitrary concave delay functions, maintaining an $O(\log n)$ competitive ratio, and to $k$-way matching with delays, yielding an $O(k \log n)$-competitive deterministic algorithm.

Closest papers

Nearest neighbours by meaning across the whole index.

Noncrossing is All You Need: Beyond Identical Delay Functions in Online Matching with Delays on General Metrics

cs.DS ·2026-11-04 ·Yossi Azar, Junhao Gan, Shahar Lewkowicz, Xiao Sun, Seeun William Umboh
similarity 0.84
Abstract

Online optimization with delays has emerged as a powerful paradigm with numerous applica- tions, including matching, caching, server management, network design, and set cover. In most of these problems, competitive algorithms are known for arbitrary monotone delay functions, even when different requests are associated with different delay functions. The notable exception is online matching with delays, where all previously known algorithms achieving constant or polylogarithmic competitive ratios require the delay functions to be identical, either linear or concave, and known in advance. We study the online minimum-cost perfect matching with delays problem on general metrics. We introduce the broad class of noncrossing delay functions, which strictly generalizes the classic setting of identical concave delay functions while naturally modeling scenarios in which different requests may experience different delay costs. We present the first deterministic $O(1)$-competitive algorithm for the single-location online matching problem with noncrossing delay functions in the non-clairvoyant setting as well as a randomized $O(lognlogΔ+log^2Δ)$-competitive algorithm of an arbitrary metric space where $n$ is the number of points of the metric space and $Δ$ is its aspect ratio. Our result allows each request to have an arbitrary noncrossing delay function, thereby simultaneously removing the assumptions of identical delay functions, concavity, and clairvoyance that were required by all previous constant or polylogarithmic-competitive algorithms.

0.03

A Deterministic O(log m)-Competitive Algorithm for Online Minimum Cost Bipartite Matching with Delays

cs.DS ·2026-11-01 ·Tung-Wei Kuo
theory similarity 0.75
Abstract

In the online Minimum cost Bipartite Perfect Matching with Delays (MBPMD) problem, $m$ requests and $m$ servers arrive over time in a metric space. An online algorithm has to match each request to a server and can postpone a matching decision by paying the delay cost. The objective is to minimize the total distance and delay cost. Azar, Chiplunkar, and Kaplan gave a randomized $O(\log n)$-competitive algorithm for metric spaces with $n$ points that are known in advance. For deterministic algorithms, however, the best known competitive ratio in general metric spaces was $O(m^{0.59})$, due to Azar and Jacob-Fanani. On the line, Kuo proposed the Virtual Robust Matching (VRM) algorithm and showed that it is $O(\sqrt{m}\log^2 m)$-competitive. We prove that VRM is $O(\log m)$-competitive for the MBPMD problem in any metric space. VRM is deterministic and does not need to know the metric space or $m$ in advance. It is the first deterministic polylogarithmic-competitive algorithm for the MBPMD problem in general metric spaces. Unlike the previous analysis of VRM, our analysis does not rely on a geometric decomposition of the metric space. Instead, it charges the waiting time of requests over time to the edges of a fixed optimal matching. We also extend VRM to the non-bipartite version and prove that the resulting deterministic algorithm is $O(\log m)$-competitive. This improves the $O(\log^5 m)$ bound of Dufay and Wattenhofer and matches a concurrent result of Ahmadian, Chawla, Kumar, Purohit, and Zhang. The proof that VRM is $O(\log m)$-competitive and its non-bipartite extension were found by GPT-6 Astra (OpenAI) with almost no human input. We used Claude Opus 5.5 (Anthropic) to simplify and present the results. See the AI Usage and Methodology section for details. We take full responsibility for this paper.

0.20

Dynamic Matching with Abandonment: Optimal Guarantees via Static Priority Policies

cs.DS cs.CCcs.GTecon.TH+1 ·2026-10-09 ·Nick Arnosti, Rad Niazadeh, Pranav Nuti, Felipe Simon
benchmarktheory similarity 0.73
Abstract

We study stochastic dynamic matching with abandonment, a fundamental model in which agents of different types arrive over time, may abandon the market while waiting, and can be matched in pairs for rewards that depend on their types. No online policy can guarantee more than $0.5$ of the omniscient benchmark, which knows all arrival and departure times. Whether this guarantee is achievable has been a central open problem, even in special cases. We resolve this problem by showing that, on every instance, a simple static priority policy, which is computable in polynomial time, earns at least $0.5$ of the omniscient benchmark. This establishes that the optimal competitive ratio is exactly $0.5$, improving the previous best guarantee of 0.192 for the general model [Li et al. 2026; Collina et al. 2020] Our analysis rests on a key stochastic result, which is a new lower bound on the probability that some agent from a given set of types is available. Building on this bound, we develop two approaches: a primal approach that reads the priorities from an optimal solution of a novel linear program, and a dual approach that assigns a ``value'' to each type, and prioritizes matches with high ``surplus'' (reward minus value of involved agents). These values are the unique solution of a fixed-point equation derived from linear programming duality. We also show that the two approaches are closely connected.

0.37

Online Metric Matching with Unknown i.i.d. Arrivals

cs.DS ·2026-11-03 ·Tsubasa Harada
similarity 0.73
Abstract · 14 pages

We study online metric matching with $n$ servers and $n$ requests drawn independently from an unknown distribution. Each request must be matched immediately and irrevocably to an unused server, and the algorithm receives no samples before the process starts. We give a randomized algorithm that is $O((\log\log\log n)^2)$-competitive on arbitrary metric spaces and $O(1)$-competitive on tree metrics. These guarantees match the corresponding bounds for known i.i.d. request distributions in [GGPW19] up to constant factors. More generally, our competitive ratio is $O(α(n))$ whenever the Fair-Bias algorithm introduced in that work has competitive ratio $α(n)$ for known i.i.d. arrivals on the same class of metrics. Consequently, proving that Fair-Bias is constant-competitive on general metrics would also yield a constant-competitive algorithm for unknown i.i.d. arrivals.

0.18

Improved Bounds for Online Matching with Random Edge Arrivals

cs.DS ·2026-11-10 ·Yilong Feng, Haolong Li, Zonghan Yang
similarity 0.69
Abstract

We study the unweighted online matching problem with random edge arrivals, where each edge arrives at an independent time drawn uniformly from $[0,1]$, and the algorithm must immediately and irrevocably accept or reject it while maintaining a matching. Guruganesh and Singla (IPCO, 2017) first broke the $1/2$ barrier of the naive Greedy algorithm by giving a $(1/2+\varepsilon)$-competitive algorithm for a small constant $\varepsilon>0$, a guarantee that has remained the best known for nearly a decade. We give a simple three-phase algorithm that achieves a competitive ratio of $0.5445$ by deliberately rejecting selected early edges to reserve their endpoints for later matching opportunities. With a different choice of parameters, the same algorithm is $0.5535$-competitive on triangle-free graphs, including bipartite graphs. We also establish competitive ratio upper bounds below $0.6964$ for general graphs and $0.7043$ for bipartite graphs via exact rational evaluation of an optimal-policy recurrence on fixed graphs, even when the input graph is known up to isomorphism.

0.22

Online Matching with Arbitrary Stochastic Rewards

cs.DS math.OC ·2026-11-02 ·Rajan Udwani
benchmark similarity 0.69
Abstract

Online matching with stochastic rewards is a generalization of online bipartite matching in which an attempt to match an online arrival to an offline resource may fail with some probability. Each arrival allows at most one attempt and the success probabilities of its edges are revealed when it arrives. Greedy is 0.5-competitive, which is the best possible for deterministic algorithms. While better competitive ratios are known in several special cases, beating 0.5 for arbitrary probabilities has remained open. We show that, against the adaptive offline benchmark and for arbitrary probabilities, a randomized Perturbed Greedy algorithm is at least 0.591-competitive in the unweighted setting and at least 0.531-competitive with vertex weights. The perturbation functions combine Greedy with scaled versions of the classic exponential function.

0.07

Computational Hardness of Online Stochastic Matching

cs.DS cs.CCcs.GT ·2026-11-17 ·Yifeng Teng, Zongjun Yang
theory similarity 0.68
Abstract

In the online stochastic matching problem on a bipartite graph, offline vertices are given in advance, and online requests arrive sequentially from known distributions, each matched immediately and irrevocably to a free neighbor or rejected. Computational hardness results of the optimal online strategy have been known only for instances where online vertices have a fixed arrival order [Papadimitriou et al., 2024]. For random-order arrivals or even i.i.d. arrivals, it has been long open since the problem was proposed [Feldman et al., 2009]. In this paper, we give the first computational hardness results for online stochastic matching with random-order arrivals. In particular, we prove that for known i.i.d. arrivals, computing the online optimum is APX-hard, ruling out a Polynomial-Time Approximation Scheme unless P = NP, even in unweighted graphs with two offline neighbors per online vertex. For random-order arrivals, even when there is only one offline node (i.e., the prophet secretary setting), computing the optimal online policy is #P-hard, resolving an open problem since [Dütting et al., 2023].

0.24

Optimal analysis of Greedy for stochastic online Euclidean matching: flat torus to the rescue

cs.DS ·2026-09-20 ·Mingwei Yang, Sophie H. Yu
theory similarity 0.68
Abstract

We study online metric matching with $n$ servers and $n$ requests, all sampled independently and uniformly from $[0,1]^d$. We analyze the Greedy algorithm, which matches each arriving request to its closest available server. Despite its strong empirical performance, non-trivial bounds on Greedy's competitive ratio were previously known only for $d = 1$, where it is $O(1)$-competitive [BFP23]. We prove that Greedy is $O(1)$-competitive for every fixed $d\geq3$ and has competitive ratio $Θ(\sqrt{\log n})$ for $d=2$. Our proof first analyzes Greedy on the flat torus and then transfers the resulting estimates to the cube.

0.40