CS Paper Radar

Online geometric matching and segments block points

Yaqiao Li, Junyi Lin

cs.DS cs.CG ·submitted 2026-10-16 08:34 UTC · v1
publishedhot direction

Abstract

Given a sequence of online points in general position in the plane, the geometric matching problem asks to match as many points as possible, subject to segment crossing constraints. We initiate the study of online geometric matching with limited crosses. In the $k$-crossing model each matched segment is allowed to have at most $k$ crosses, where $k=0$ corresponds to the online noncrossing matching model for which Bose et al. proved that Greedy is an optimal deterministic algorithm achieving a competitive ratio of $2/3$. In the triangle-free-crossing model no three matched segments are allowed to pairwise cross each other. Interestingly, we show in both cases the performance of Greedy does not improve by allowing crosses, and in fact, becomes worse in the $k$-crossing setting for $k\ge 1$. In the triangle-free-crossing model, we propose a simple two-layer-Greedy deterministic algorithm achieving a competitive ratio $4/5$. More interestingly, we propose and study the underlying segments blocking points extremal problem, and discuss its connection to vertex cover numbers and Ramsey numbers, with interesting open problems that might be of independent interest. We revisit the noncrossing model. We give a randomized algorithm which is an asymmetric version of Kamali et al., improving the competitive ratio from $0.66952$ to $0.67034$. We also show, via a conceptually simple construction, that no randomized algorithm can match more than $6/7$ fraction of points, improving the previous $16/17$ by Boyar et al.

Comment
accepted by IJTCS-FAW 2026

Closest papers

Nearest neighbours by meaning across the whole index.

Improved Bounds for Online Matching with Random Edge Arrivals

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

Low-Crossing Spanning Paths via Quasi-Uniform Sampling and their Applications

cs.CG cs.DS ·2026-10-23 ·Mónika Csikós, Nabil H Mustafa
similarity 0.70
Abstract

Given a set system (X, S), we consider the problems of constructing perfect matchings and spanning paths (also known as Welzl orders) of X with low crossing numbers with respect to S. Matchings with low crossing numbers were originally introduced in the late 1980s in the seminal works of Welzl [29, 30] and Chazelle-Welzl [7], who showed that any set system (X, S) with bounded dual VC-dimension d has a matching with crossing number O |X| 1-1/d , which is optimal. Low-crossing matchings and spanning paths have found several applications outside of their initial realm of computational geometry, including algorithmic graph theory, model checking, and game theory. In many of these applications, |S| is near-linear in |X|, which motivated the search for an improved construction for this regime. However, the proposed new algorithms provided only average-case bounds or sub-optimal crossing number guarantees for d $\ge$ 2 [5, 12]. We propose a new quasi-uniform sampling based framework. This allows us to obtain a simple algorithm with expected running time of __ |X| 2 + |S| $\bullet$ |X| , which improves upon the previous-best Our result has several immediate consequences, including new faster algorithms for constructing low-crossing spanning paths for set systems induced by balls, as well as for neighborhood set systems of graphs. Moreover, we get the first quadratic-time algorithm for combinatorial discrepancy, with nearly optimal discrepancy (up to a log factor), for bounded dual VC-dimension set systems. Beyond these applications, we believe that our idea could be applied to other algorithms that use the multiplicative weight update method.

0.25

Online Matching with Arbitrary Stochastic Rewards

cs.DS math.OC ·2026-11-02 ·Rajan Udwani
benchmark similarity 0.67
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

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

A short proof of the 1-1/e performance of RANKING on the complete upper triangular instance

cs.DS ·2026-11-17 ·Giovanni Montanari, Nadav Merlis, Simon Mauras, Vianney Perchet
similarity 0.66
Abstract

The randomized online bipartite matching algorithm RANKING of Karp, Vazirani and Vazirani (1990) matches, asymptotically, a fraction $1-1/e$ of the vertices of the complete upper triangular (CUT) instance. We give a short proof of this fact that looks at the final matching from the offline side. A single observation drives the argument: the first $k$ arrivals can distinguish the offline vertices $v_k,\ldots,v_n$ only through their ranks. As a consequence, whether $v_k$ is matched is decided by a uniform draw among the remaining ranks, and the number of matched vertices among $v_1,\ldots,v_k$ is a Markov chain with explicit transition probabilities. A linear differential equation, solved by hand, gives the limiting profile of this chain, and the constant $1/e$ appears where the matching probability reaches one.

0.27

Online Transportation via Shifted Geometric Scales

cs.DS ·2026-11-12 ·John Jeang
theory similarity 0.66
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

Online and Incremental Fractional Vertex Cover on Trees

cs.DS ·2026-08-25 ·Júlia Baligács, Bartłomiej Bosek, Yann Disser, Andreas Emil Feldmann, Grzegorz Gutowski +3 more
publishedtheory similarity 0.64
Abstract

In this paper we study the fractional vertex cover problem on trees in two related models: online and incremental. In the online model, the vertices of the tree are known a priori and the edges arrive one at a time. The goal is to maintain a fractional vertex cover of the tree, i.e., an assignment of fractional weights from [0,1] to the vertices such that the weights of endpoints of every edge sum up to at least one. After each edge arrival, we need to modify the fractional vertex cover to cover the new edge as well. However, we can only increase the values assigned to vertices. The problem was studied before (in the vertex arrival model) by Wang and Wong, who motivated it as a generalization of the ski-rental problem, but also (more importantly) by its close connection to the dual online matching problem. They presented a 1.901-competitive algorithm for general graphs in the vertex arrival model. We present an $\frac{11}{6} \approx 1.83$-competitive algorithm for trees in the more general edge arrival model. In addition, we study the fractional vertex cover problem in an incremental model, where we again seek a fractional vertex cover after every update, but all the updates to the tree are known to the algorithm a priori. In this model, we give a 1.5-competitive algorithm and provide a matching lower bound.

0.46

Minimum blockers and extremal graphs for nonnested matchings

cs.DM math.CO ·2026-09-13 ·Pedro M. M. de Castro
theory similarity 0.63
Abstract · 30 pages, 11 figures, 1 algorithm. Substantially expanded version: new constructions with quadratic excess beyond the proposed extremal boun…

We classify all smallest sets of edge deletions that destroy every nonnested perfect matching in a complete ordered graph. The vertices have a fixed linear order. A perfect matching selects edges that use each vertex exactly once; it is nonnested when no selected edge has both endpoints strictly between those of another. On $2k$ vertices, exactly $k$ deletions are necessary, and we describe all $2^k+k-2$ minimum deletion sets for every $k\ge2$. Allowing a matching to leave vertices unused changes the extremal problem. Barát, Freschi and Tóth proposed that an $n$-vertex ordered graph avoiding a nonnested $k$-edge matching can have at most $(k-1)n$ edges. We construct counterexamples for every $k\ge5$ and $n\ge2k+1$. For $n\ge3k$, our constructions exceed the proposed value by a number of edges proportional to $k^2$, matching the order of the known upper bound on this excess. The classification follows from cuts between consecutive intervals; the larger constructions coordinate deletions at the two ends of the vertex order. The exact extremal value remains open in general.

0.30