CS Paper Radar

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

Mingwei Yang, Sophie H. Yu

cs.DS ·submitted 2026-09-20 23:44 UTC · v2
theory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.DS ·2026-11-03 ·Tsubasa Harada
similarity 0.76
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

Near-Optimal Online Metric Matching on $Δ$-ary HST

cs.DS cs.CCcs.DM ·2026-09-21 ·Parth Gor, Sourya Roy, Kasturi Varadarajan
similarity 0.74
Abstract

In the online metric matching problem, we have $n$ servers with known locations in some metric space. Requests arrive one-by-one at certain locations, and upon arrival a request must be matched to a server that was not matched to a previous request. The goal is to minimize the matching cost. For randomized algorithms with an oblivious adversary, the best known competitive ratio is obtained by embedding the metric space into an HST, and then solving the problem in the setting where the metric space is defined by the HST. Bansal et al. (Algorithmica, 2014) introduced a framework for online metric matching where one develops an algorithm in a restricted reassignment model, and then transforms this into a true online algorithm. Using this framework, they obtained an expected competitive ratio of $O(\log n)$ for HSTs; this also gives the best known competitive ratio of $O(\log^2 n)$ for general metrics. In this paper, we revisit this framework with the aim of developing new algorithms. For HSTs where each node has at most $Δ$ children, we develop an algorithm via this framework with an expected competitive ratio of $O((\log\log Δ) \cdot \log Δ)$. In particular, this ratio is independent of $n$, the number of servers/requests. It is near-optimal, as the expected competitive ratio of any algorithm is $Ω(\log Δ)$.

0.16

Degree-Parameterized Analysis of Sampling-Based Online Matching

cs.DS cs.GT ·2026-09-13 ·Pan Xu
publishedtheory similarity 0.73
Abstract · A preliminary version of this work has been accepted to WINE 2026

We study edge-weighted online bipartite matching under random arrival order, parameterized by the maximum offline degree $d$ and sampling fraction $θ$. We analyze two sampling-based frameworks. For \emph{Deterministic Greedy Sampling}, which computes prices from a fixed-size initial sample and then applies a local threshold rule, we derive an explicit worst-case competitive ratio and prove it tight within this policy family for every fixed $d\ge2$ and $θ\in[0,1]$. The optimal sampling choice interpolates between no sampling for $d=1,2$ and a dense-limit guarantee of approximately $0.2562$, improving on the classical $1/8$ analysis while retaining linear per-arrival time. We also derive worst-case bounds on the variance of the number of matched offline agents, including order-tight behavior as $θ\to1_-$ and an $O(θ)$ bound as $θ\to0_+$ for fixed $m,d$. For \emph{Black-Box Sampling--Matching}, we introduce prefix-dependent reweighting followed by an arbitrary approximate offline matching solver and prove a transfer theorem whose guarantee is the offline approximation ratio times an explicit function of $d$ and $θ$. With exact matching, the framework recovers the classical $1/e$ guarantee in the unbounded-degree limit.

0.28

Online Transportation via Shifted Geometric Scales

cs.DS ·2026-11-12 ·John Jeang
theory similarity 0.72
Abstract · The majority of this work was generated and edited by iteratively prompting ChatGPT-6 Astra. After review, we believe the results to be corr…

In the Online Transportation problem, introduced by Kalyanasundaram and Pruhs (1995), requests arrive sequentially in a metric space and must be assigned immediately and irrevocably to one of $m$ facilities with available capacity. The objective is to minimize the total distance between requests and their assigned facilities. The problem generalizes the Online Metric Matching problem, in which each facility has unit capacity, and inherits a $2m-1$ lower bound on the competitive ratio for all deterministic algorithms. For Online Metric Matching, Kalyanasundaram and Pruhs (1993) and Khuller, Mitchell, and Vazirani (1994) established an optimal deterministic competitive ratio of $2m-1$, attained by the Retrospective (Permutation) algorithm. Kalyanasundaram and Pruhs (1998) conjectured that the same ratio is achievable for online transportation. Recently, Seth, Das, and Raghvendra (2026) obtained a competitive ratio of approximately $6.66m-2.89$ using their Robustified Greedy algorithm. We give an algorithm with competitive ratio $ρ(m-1)+1$, where $ρ\approx5.64$. Our algorithm builds on minimum-spanning-tree search techniques developed by Harada and Itoh (2025) and Arndt, Moseley, Pruhs, and Uetz (2026), using priority-based virtual depth-first searches over the known facilities. However our algorithm uses a phase to shift the geometric search scales, to decide when to skip certain searches and optimize the thresholds that define what edges to include in a given search.

0.14

Improved Bounds for Online Matching with Random Edge Arrivals

cs.DS ·2026-11-10 ·Yilong Feng, Haolong Li, Zonghan Yang
similarity 0.71
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.71
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

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.70
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

Computational Hardness of Online Stochastic Matching

cs.DS cs.CCcs.GT ·2026-11-17 ·Yifeng Teng, Zongjun Yang
theory similarity 0.69
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