Jul 2026· International Colloquium on Automata, Languages and Programming· pp. 128:1-128:21· 1 citation· 27 references
Computer Science
TL;DR
This result is the first result which shows hardness for instances where the optimal algorithm employs preemption, and improves upon the strongest previously known upper bound of $2-\sqrt{2} \approx 0.585$.
Abstract
We study the online preemptive matching problem, in which the edges of a graph arrive sequentially and the algorithm must maintain a matching by accepting or rejecting arriving edges and possibly discarding previously accepted ones. We prove a new upper bound of $0.5661$ on the competitive ratio achievable for the problem. This bound applies to arbitrary randomized algorithms, bipartite graphs and if we allow the algorithm to output a fractional solution. Our result improves upon the strongest previously known upper bound of $2-\sqrt{2} \approx 0.585$, due to Huang et al. [SODA'19]. Previous hardness constructions relied on edge sequences described by vertex arrivals where each arriving vertex reveals its edges to yet unvaried vertices. Under such sequences, Huang et al. showed that there exists a non-preemptive online algorithm with competitive ratio $\sim0.567$ (or $2-\sqrt{2}$ for fractional solutions). Consequently, our hardness construction is the first result which shows hardness for instances where the optimal algorithm employs preemption.
This paper studies fractional matching on general graphs in the fully online model of Huang et al. (JACM 2020), in which all vertices arrive online and remain available for only a limited time, and extends the classic Water-Filling algorithm to the fully online setting, establishing that Water-Filling is not optimal in...
We prove that no randomized integral or fractional algorithm for online vertex cover under general vertex arrivals achieves a competitive ratio strictly below $1+\sqrt{e}/2\approx1.824360635$, even on bipartite graphs and against an oblivious adversary. This improves the previous lower bound of approximately $1.753$. O...
The demand matching problem generalizes both the knapsack problem and the $b$-matching problem. In this problem, each edge of a graph has a demand and a weight, and each vertex has a capacity. The goal is to find a maximum weight subset of edges such that, at each vertex, the total demand of the incident selected edges...
We study the online Busy Time scheduling model on a single machine of unbounded capacity, with non-preemptive jobs. In our setting, flexible jobs arrive online with a processing time and deadline, both of which become known to the algorithm at the job's arrival time. The goal is to schedule jobs on the machine to finis...
A. Calinescu, G. Călinescu, Peng-Jun Wan· 0 citations
We study one-sided online bipartite matching with recourse. In this setting, one side of a bipartite graph is known in advance, while vertices on the other side arrive online together with their incident edges. After each arrival, the algorithm must maintain a maximum-cardinality matching while minimizing the total num...
Júlia Baligács, B. Bosek, Paweł Putra et al.· 0 citations
An iterative relaxation algorithm for the demand matching problem that exploits a structural characterization of strictly fractional extreme points of the natural LP relaxation, which reduces the residual rounding problem to odd-cycle instances and gives a greedy, combinatorial $(k, 1)$-bicriteria approximation algorit...
Yu-Chong Pan, M. Goemans· 1 citation
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
