Online Preemptive Matching Revisited

Concurrently and independently with our work, Assadi, Xiang and Jiang have listed a paper titled “Semi-Streaming Matching in a Single Pass: A New Framework for Lower Bounds via Blueprints” (appearing at STOC26) on their website which might have implications for the preemptive model.

Preemptive matching is known to admit better then $1/2$-approximate algorithms for structured inputs. Jiang and Zhang [17], Chiplunkar et al. [8], Tirodkar and Vishwanathan [26] and Buchbinder et al. [7] have studied the problem for acyclic graphs. Pashkovich and Snow [23] have considered inputs with bounded maximum degree and derived positive results beating the greedy algorithm even in the lack of preemption.

Our approach builds on the following observation: existing hard instances for this problem do not merely establish an upper bound on the competitive ratio, but also force the algorithm to produce solutions with a very rigid structure. In particular, in both [10, 14], the $4n$ vertices of the bipartite input graph can be partitioned into four equal-sized independent sets: $T_1,T_2$ (the tight vertices) and $L_1,L_2$ (the loose vertices). Edges exist only between the pairs $T_1$–$T_2$, $T_1$–$L_1$, and $T_2$–$L_2$ (see Figure 1), and the graph admits a perfect matching between tight vertices $T_1\cup T_2$ and loose vertices in $L_1\cup L_2$.

Although not proven in their respective papers, it can be shown that both constructions share the following property: in order to achieve the optimal competitive ratio $\alpha$, the algorithm must output a solution in which the tight vertices have average weight arbitrarily close to $1$. Therefore, if our goal is to prove any strict separation from the previous best upper bound $\alpha =2-\sqrt{2}$, we may safely assume that, when applied to these instances, the algorithm produces a solution in which the tight vertices have average weight close to $1$.

For simplicity, suppose we insert such an instance and the algorithms output is completely uniform: vertices in $T_1\cup T_2$ have average weight $1$, while vertices in $L_1\cup L_2$ have average weight $2\alpha -1$. Our goal is to penalize the algorithm for assigning weight $1$ to the tight vertices. We freeze all vertices in $T_2$, and introduce a new set of vertices $U$ of size $|T_1|$, connected to $T_1$ by a complete bipartite graph. Since vertices in $T_2$ are frozen, the algorithm doesn’t want to preempt weight from edges incident to them. Consequently, the only way to assign weight to edges between $T_1$ and $U$ is by preempting weight from edges between $T_1$ and $L_1$.

Regardless of the algorithm’s preemptive decisions, once $U$ and its incident edges are introduced, either the vertices in $L_1$ or those in $U$ must have average weight at least $(2\alpha -1)/2$ (we can safely assume the algorithm keeps the vertices of $T_1$ tight). For simplicity, assume that the vertices in $L_1$ end up with uniform average weight $(2\alpha -1)/2$. We then freeze vertices of $T_1$ and insert a copy of the initial hard instance between the vertices of $L_1$.

At this stage, the graph admits a perfect matching: vertices in $T_1$ can be matched to $U$, and vertices in $L_1$ can be matched among themselves. Thus, the maximum matching size is $5n/2$. Prior to the second insertion of the initial instance within $L_1$, the algorithm cannot increase its total weight by shifting weight from $T_1$–$L_1$ edges to $T_1$–$U$ edges. Hence, before the final step, the algorithm’s total weight is at most $2\alpha n$, since the initial instance is $\alpha$-hard.

When the $\alpha$-hard instance is recursively inserted into $L_1$, the vertices of $L_1$ already carry “frozen” average weight $(2\alpha -1)/2=r$. Intuitively, the algorithm can increase this weight by at most $\alpha (1-r)$, as the subgraph induced by $L_1$ is itself $\alpha$-hard. Therefore, the competitive ratio of the output at this point is upper bounded by

In the simplified construction above, the algorithm may slightly deviate from the assumed structure. We therefore establish a strong relationship between the extent to which tight vertices deviate from being fully tight and the resulting loss in competitive ratio. In Section 4, we show that if the algorithm produces a solution in which tight vertices have weight at most $1-x$, then its competitive ratio degrades to $\alpha (1-x/2)$, for the $\alpha =1/(1+\ln 2)\approx 0.59$ hard instance of Epstein et al. [10]. This requires reformulating their analysis in the fractional setting and generalizing it to algorithms that do not necessarily optimize their competitive ratio.

Further improvements come from scaling the size of $U$ to $\lambda |T_1|$ for an integer $\lambda >1$. In this case, during the recursive step we insert the $\alpha$-hard instance among the $\lambda |T_1|$ heaviest vertices in $U\cup L_1$. Intuitively, increasing the size of $U$ causes a larger fraction of the initial weight of $L_1$ to reside on vertices that block the algorithm’s ability to improve its solution when the hard instance is inserted for the second time.

Observe that the final step of the construction does not rely on the internal structure of the underlying $\alpha$-hard instance. Instead, the argument implies the existence of a strictly harder instance with competitive ratio . This means the resulting hard instance can be substituted into the last step of the construction, allowing for a recursive formalization. We formalize this recursion scheme in Lemma 8, and in Section 4.3 we approximate the strongest competitive ratio bound achievable by this approach.

The upper bound of $0.5661$ established in this paper can likely be improved through a more refined analysis. Since our primary goal was to demonstrate a strict separation compared to the limitations of existing approaches using the simplest possible construction, we did not fully explore all possible approaches. For instance, this is why Lemma 7 relies on the simpler (but weaker) hard instance of [10], rather than the more intricate state-of-the-art construction of [14].

We would like to highlight the fact that the previous upper bound of $2-\sqrt{2}$ by Huang et al. [14] is a constant that serves as a significant barrier in the approximation for the matching problem in multiple computational models. Namely, Konrad and Naidu [21] have shown a $2$-pass semi-streaming streaming algorithm and multiple papers [4, 6, 3] have derived fully dynamic poly-logarithmic update time algorithms with the same approximation ratio.

It might also not be instantly clear why is it the case that if we are to insert an $\alpha$-hard instance between in independent set of size $n$ with frozen weight $r$ the algorithm may only improve its output by an additive factor of $\alpha (1-r)$ if the underlying vertices don’t share the same frozen weight. We overcome this difficulty through creating multiple copies of the instance and treating the independent sets as meta vertices (for a formal derivation see Section 5.1).

Finally, the reader may observe that the simplified construction above yields a non-bipartite input graph. In the full construction, instead of inserting the $\alpha$-hard sub-instance within $U$, we insert it between $U$ and a corresponding set $U^{\prime }$ belonging to a copy of the initial instance (see Section 4.2), thereby preserving bipartiteness.

Let $w_{T_1,T_2}$, $w_{T_1,L_1}$ and $w_{T_2,L_2}$ stand for the total weight of edges running between vertex sets $T_1,T_2$, $T_1,L_1$ and $T_2,L_2$ respectively. As all edges run between these bipartition, we have that $w_{T_1,T_2}+w_{T_1,L_1}+w_{T_2,L_2}=2ny$. From the definition of $x_1$ and $x_2$ we also know that $w_{T_1,T_2}+w_{T_1,L_1}=n(1-x_1)$ and $w_{T_1,T_2}+w_{T_2,L_2}=n(1-x_2)$.

Combining the equalities we get that $w_{T_1,L_1}=n(2y-1+x_2)$ and $w_{T_2,L_2}=n(2y-1+x_1)$. As all edges of loose vertices run to their corresponding tight sets we can conclude theclaim. $\mathrm{⊲}$

At this point, the adversary creates a copy of the instance together with the algorithm’s current output. Whether such copying is permissible varies across the literature. In Section A.2, we explain why, from a hardness perspective, it is without loss of generality to assume that the adversary may duplicate instances – including the algorithm’s output – in the context of the online preemptive fractional matching problem.

Let the copied instance be denoted by $G(T_1^{\prime }\cup T_2^{\prime }\cup L_1^{\prime }\cup L_2^{\prime },E^{\prime })$. The adversary then inserts vertex sets $U$ and $U^{\prime }$ of size $\lambda n$ for some integer constant $\lambda$. At this point the algorithm freezes the vertices of $T_2,L_2,T_1^{\prime },L_1^{\prime }$. Afterwards the adversary inserts complete bipartite sub-graphs between vertices of $T_1-U$ and $T_2^{\prime }-U^{\prime }$. The algorithm will react to this insertions. After this reaction let the vertex sets $U_{L_1}$ and $U_{L_2^{\prime }}^{\prime }$ refer to the $\lambda n$ highest weight vertices of $L_1\cup U$ and $L_2^{\prime }\cup U^{\prime }$ respectively.

Without loss of generality focus on the average weight of $U_{L_1}$. Consider how the algorithm may have reacted to the insertion of the complete bipartite sub-graph between $U$ and $T_1$. As $T_2$ is frozen at this point, the algorithm doesn’t want to preempt weight from $T_2-T_1$ edges. The algorithm also wants to make at least one endpoint of all the edges in this complete bipartite graph tight to maximize its competitive ratio. The average weight of $U_{L_1}$ is minimized if the algorithm decides to make the $T_1$ endpoints tight.

Before the insertion the average weight of $T_1$ vertices is $1-x_1$ so the algorithm can safely place a total weight of $n{x}_1$ on the newly arrived edges to $U$. Afterwards, it might choose to preempt some weight from $T_1-L_1$ edges to distribute them into $T_1-U$ edges. Either way, the total weight of edges between $T_1$ and $L_1\cup U$ will be $n(2y-1+x_1+x_2)=n(2y-1+2x)$ by Claim 10. As $U_{L_1}$ consists of the $\lambda n$ highest weight vertices of $U\cup L_1$ they will be hosting at least a $\lambda /(\lambda +1)$ fraction of this weight implying the claim. $\mathrm{⊲}$

Now the adversary freezes vertices $T_1,T_2^{\prime }$ and creates further $n-1$ copies of the whole instance so far (lets refer to this as the medium stage), in each including the output of the algorithm. Let ${(U_{L_1})}^1,\mathrm{\dots },{(U_{L_1})}^n$ and ${(U_{L_2^{\prime }}^{\prime })}^1,\mathrm{\dots },{(U_{L_2^{\prime }}^{\prime })}^n$ correspond to the copies of $U_{L_1}$ and $U_{L_2^{\prime }}^{\prime }$ in these instances. Finally, the adversary inserts the initial $\alpha$-hard instance between the vertices of $\bigcup {(U_{L_1})}^i$ and $\bigcup {(U_{L_2^{\prime }}^{\prime })}^i$.

The detail of this process are formally explained in Section 5.1 and the guarantees of its outcome are summarized by Lemma 15. Essentially, the algorithm treats vertex sets ${(U_{L_1})}^i,{(U_{L_2^{\prime }}^{\prime })}^i$ as meta vertices in a bipartite meta graph $𝒢$ and inserts the $\alpha$-hard instance into $𝒢$. The insertion of an edge between a pair of meta vertices is simulated through an insertion of a complete bipartite graph between the corresponding vertex sets. Now we turn to analyzing the competitive ratio.

The resulting graph has $2(4+\lambda )n^2$ vertices. The initial instance was on $4n$ vertices which were first copied once. The addition of vertex sets $U,U^{\prime }$ increased the vertex site size to a further $2(4+\lambda )n$ and the medium stage instance was copied $n-1$ times. So its sufficient to argue that there exist a perfect matching in the graph at the end. Note that in each copy of the medium stage instance vertex sets $T_2$ and $T_1^{\prime }$ can be perfectly matched to vertices of $L_2$ and $L_1^{\prime }$ respectively due to the definition of the initial tight-loose structure. In the meta graph from the definition of an $\alpha$-hard instance there must exist a perfect matching of the meta vertices. As meta edges represent a complete bipartite sub-graph between the corresponding vertex sets vertices of $\cup {(U_{L_1})}^i$ can be perfectly matched to vertices of $\cup {(U_{L_2^{\prime }}^{\prime })}^i$.

It remains to argue that for all copies of the medium stage instance vertex sets copies $T_1$ and $T_2^{\prime }$ can be matched to their corresponding $(U\cup L_1)\setminus U_{L_1}$ and $(U^{\prime }\cup L_2^{\prime })\setminus U_{L_2^{\prime }}^{\prime }$ sets unmatched so far. Without loss of generality focus on the former pair. We know that there exist a perfect matching $M_{T_1-L_1}^{\ast }$ between $T_1$ and $L_1$ from the definition of the tight-loose structure and there is a complete bipartite sub-graph between $T_1$ and $U$. Let $M_{T_1-(L_1\setminus U_{L_1})}^{\ast }$ be denoted to the restriction of this perfect matching to vertices of $L_1\setminus U_{L_1}$. Match the $T_1$ endpoints of $M_{T_1-(L_1\setminus U_{L_1})}^{\ast }$ through the edges of $M_{T_1-(L_1\setminus U_{L_1})}^{\ast }$. The remaining vertices of $T_1$ can be arbitrarily matched within the complete subgraph $T_1\cup (U\setminus U_{L_1})$. $\mathrm{⊲}$

Finally, with the following claim upper bounding the performance of the algorithm, we may conclude the lemma.

After the initialization of the tight-loose instance by Lemma 7 the competitive ratio of the algorithm is at most $y$, hence the algorithms output has weight at most $2yn$. Once its copied the first time this jumps to $4yn$. When the complete bipartite sub-graphs between $U,T_1$ and $U^{\prime },T_2^{\prime }$ are inserted the algorithm may increase its output weight by $n(x_1+x_2)=2nx$ to $4yn+2nx$. At this point the medium stage instance is copied $n-1$ times blowing this value up by $n$.

Finally, by Lemma 15 when the $\alpha$-hard instance is inserted into the meta graph ${𝒢}^{\prime }$ the algorithm may increase the total weight of its output by $n^2\alpha \lambda (1-\frac{2y-1+2x}{\lambda +1})$. Recall that all sets of vertices in ${(U_{L_1})}^i,{(U_{L_2^{\prime }}^{\prime })}^i:i\in [n]$ have average weight at least $\frac{2y-1+2x}{\lambda +1}$ before the insertion of the $\alpha$-hard instance by Claim 11. $\mathrm{⊲}$

Define $y=\frac{1-x/2}{1+\ln 2}$. Note that ${\alpha }_0=\frac{1-\frac{x_{max}}{2}}{1+\ln 2}$. The expression can now be re-stated as

Fix $\lambda =129$. Note that the choice of the constant $\lambda$ is sensitive, but any sufficiently large but comparably smaller value then $1/ϵ$ suffices. Consider the function,

In order to describe the tightest case of the initial min-max expression we need to consider when $f(\alpha ,y)$ is maximized. Hence, we examine $\frac{df(\alpha ,y)}{d\alpha }$.

The second inequality follows from $y\le 1/(1+\ln 2)$. This implies that the expression is maximized when $\alpha$ is minimized so we can proceed with assuming $\alpha ={\alpha }_0$. $f({\alpha }_0,y)$ is linear with respect to the parameter $y$. Consequently, it must obtain its maximum on one of the endpoints of the interval range so its sufficient to prove that

Via machine its easy to check that $f({\alpha }_0,{\alpha }_0)\sim -1.12\cdot {10}^{-5}$ and $f({\alpha }_0,1/(1+\ln 2))\sim -2.81\cdot {10}^{-5}$ concluding the proof. $\mathrm{⊲}$

We construct a bipartite meta-graph $𝒢$ with vertex sets $ℒ$ and $ℛ$, each of size $N$. Each meta-vertex in $ℒ$ (respectively, $ℛ$) corresponds to one independent set $L_i$ (respectively, $R_i$) in $G$.

We now insert the $\alpha$-hard instance into $𝒢$. Whenever an edge between meta-vertices corresponding to $L_i\in ℒ$ and $R_j\in ℛ$ arrives in the $\alpha$-hard instance, we insert a complete bipartite subgraph between the corresponding independent sets $L_i$ and $R_j$ in $G$. This process defines the edge set $E_{\alpha }$ and its arrival sequence. Since the $\alpha$-hard instance admits a perfect matching, it follows that $E_{\alpha }$ contains a perfect matching between ${\bigcup }_{i\in [N]}{L}_i$ and ${\bigcup }_{i\in [N]}{R}_i$.

Next, we relate the behavior of the algorithm on $G$ to an induced fractional matching on $𝒢$. Whenever the algorithm increases or decreases the weight of an edge $(u,v)$ with $u\in L_i$ and $v\in R_j$ by an amount $\mathrm{\Delta }\in [0,1]$, we apply a corresponding change of $\mathrm{\Delta }/(k(1-r))$ to the weight of the edge between the meta-vertices representing $L_i$ and $R_j$, in the same direction.

We first observe that these updates define a valid execution of an online preemptive fractional matching algorithm on the meta-graph $𝒢$ under the $\alpha$-hard arrival sequence. Since all neighbors of vertices in each $L_i\cup R_i$ are frozen in $G$, we may assume that the algorithm never preempts weight from edges outside of $E_{\alpha }$ during the arrivals of $E_{\alpha }$. Consequently, the average weight of vertices in each $L_i\cup R_i$ remains within the interval $[r,1]$ throughout this process, which implies that the induced vertex weights in $𝒢$ always lie in $[0,1]$.

Because the instance inserted into $𝒢$ is $\alpha$-hard, the total weight of the induced fractional matching on $𝒢$ is at most $\alpha N$. By construction, this implies that the total increase in weight across all edges of $G$ during the arrivals of $E_{\alpha }$ is at most $(1-r)k\alpha N$, completing the proof. $◀$