# Tight Bounds for Online Matching in
Bounded-Degree Graphs with Vertex Capacities

Susanne Albers Department of Computer Science, Technical University of Munich.
<EMAIL_ADDRESS>Sebastian Schubert Corresponding author. Department of
Computer Science, Technical University of Munich<EMAIL_ADDRESS>
We study the $b$-matching problem in bipartite graphs $G=(S,R,E)$. Each vertex
$s\in S$ is a server with individual capacity $b_{s}$. The vertices $r\in R$
are requests that arrive online and must be assigned instantly to an eligible
server. The goal is to maximize the size of the constructed matching. We
assume that $G$ is a $(k,d)$-graph [21], where $k$ specifies a lower bound on
the degree of each server and $d$ is an upper bound on the degree of each
request. This setting models matching problems in timely applications.

We present tight upper and lower bounds on the performance of deterministic
online algorithms. In particular, we develop a new online algorithm via a
primal-dual analysis. The optimal competitive ratio tends to 1, for arbitrary
$k\geq d$, as the server capacities increase. Hence, nearly optimal solutions
can be computed online. Our results also hold for the vertex-weighted problem
extension, and thus for AdWords and auction problems in which each bidder
issues individual, equally valued bids.

Our bounds improve the previous best competitive ratios. The asymptotic
competitiveness of 1 is a significant improvement over the previous factor of
$1-1/e^{k/d}$, for the interesting range where $k/d\geq 1$ is small. Recall
that $1-1/e\approx 0.63$. Matching problems that admit a competitive ratio
arbitrarily close to 1 are rare. Prior results rely on randomization or
probabilistic input models.

##  1 Introduction

Maximum matching is a fundamental problem in computer science. In a seminal
paper Karp, Vazirani and Vazirani [17] introduced online matching in bipartite
graphs $G=(S\cup R,E)$. The vertices of $S$ are known in advance, while the
vertices of $R$ (requests) arrive one by one and must be matched immediately
to an eligible partner. The $b$-matching problem is a generalization where the
vertices of $S$ (servers) have capacities and may be matched multiple times,
see e.g. [16]. Online bipartite matching and capacitated extensions have
received tremendous research interest over the past 30 years. In this paper we
study the $b$-matching problem in bounded-degree graphs, defined in [21]. We
assume that there is a lower bound on the degree of each server $s\in S$,
meaning that there is a certain demand for each server. Furthermore we assume
that there is an upper bound on the degree of each $r\in R$, i.e. each request
can only be assigned to a subset of the servers. This setting models matching
problems in many timely applications, as we will describe below.

More formally, we investigate the following problem. Again, let $G=(S\cup
R,E)$ be a bipartite graph, where the vertices of $S$ are servers and the
vertices of $R$ are requests. The set $S$ is known in advance. Each server
$s\in S$ has an individual capacity $b_{s}\in\mathbb{N}$, indicating that the
server can be matched with up to $b_{s}$ requests. The vertices of $R$ arrive
online, one by one. Whenever a new request $r\in R$ arrives, its incident
edges are revealed. The request has to be matched immediately and irrevocably
to an eligible server, provided that there is one. The goal is to maximize the
number of matching edges. We will also examine the _vertex-weighted_ problem
extension, where additionally each server $s\in S$ has a weight $w_{s}$ and
the value of every matching edge incident to $s$ is multiplied by $w_{s}$. Now
the goal is to maximize the total weight of the constructed matching.

We assume that $G$ is a $(k,d)$-graph, defined by Naor and Wajc [21], where
$k$ and $d$ are positive integers. Each server $s\in S$ has a degree $d(s)\geq
k\cdot b_{s}$. Each request $r\in R$ has a degree $d(r)\leq d$. Naor and Wajc
[21] defined these graphs for the general AdWords problem. Note that the
inequality $d(s)\geq k\cdot b_{s}$ expresses a degree bound in terms of the
server capacity. This is essential. As we shall see, the performance of
algorithms depends on the degrees $d(s)$ as a function of $b_{s}$. A degree
bound independent of $b_{s}$ is vacuous for larger $b_{s}$. Also, a company
operating a high-capacity server expects the server to be attractive and a
potential host for a large number of requests. Otherwise it might be
beneficial to reduce the server capacity.

The best results will be obtained if $k\geq d$. In this case the average
demand for each server slot is high, compared to the number of servers a
request can be assigned to. This setting is also very relevant in
applications. We will assume that $d\geq 2$. If $d=1$, any Greedy algorithm
constructs an optimal matching. We remark that $(k,d)$-graphs are loosely
related to $d$-regular graphs in which each vertex has a degree of exactly $d$
and a capacity of 1. This graph class has been studied extensively in computer
science and discrete mathematics, see e.g. [6, 7, 8, 11, 22].

The $b$-matching problem in $(k,d)$-graphs models many problems in modern
applications, cf. [5, 13, 21]. The following description also addresses the
degree constraints.

_Video content delivery, web hosting, remote data storage_ : Consider a
collection of servers in a video content delivery network, a web hosting
provider, or a remote data storage service. A sequence of clients arrives,
each with a request that videos be streamed, web pages be hosted, or data be
stored. Based on the servers’ geographic distribution, average performance,
technology used or pricing policies, each request can only be hosted at a
small subset of the servers or server locations. Each server has a large
capacity and is well suited to service a huge number of requests in the
arriving client sequence.

_Job scheduling_ : Consider a collection of compute servers, each with certain
capabilities, located for instance in a data center. Over a time horizon jobs
arrive, requesting service. Based on computing demands, expected response
time, hardware and software requirements, each job can only be executed on a
subset of the servers. During the given time horizon, each server can process
a large number of jobs and is a suitable platform to execute very many of the
incoming jobs.

_AdWords and ad auctions_ : Consider a search engine company or digital
advertising platform. There is a set of advertisers, each with a daily budget,
who wish to link their ads to users of the search engine/digital platform and
issue respective bids. The users arrive online and must be allocated instantly
to the advertisers. Based on his search keywords, browsing history and
possible profile, each user is interesting to a small set of advertisers. Each
advertiser has a decent budget and targets a large population of the users.
Obviously, in this application the advertisers correspond to the servers and
the users are the incoming requests. The $b$-matching problem models the basic
setting where the bids of all advertisers are either 0 or 1. The vertex-
weighted extension captures the scenario where all the bids of an advertiser
$s\in S$ have a value of 0 or $w_{s}$. These base cases are also studied in
recent work by Vazirani [23].

We analyze the performance of online algorithms using competitive analysis.
Given an input graph $G$, let Alg$(G)$ denote the size (or weight) of the
matching constructed by an online algorithm Alg. Let Opt$(G)$ be the
corresponding value of an optimal offline algorithm Opt. Algorithm Alg is
$c$-competitive if $\textsc{Alg}(G)\geq c\cdot\textsc{Opt}(G)$ holds, for all
$G$. In our analyses we will focus on bipartite $(k,d)$-graphs $G$.

Related work: As mentioned above, Karp et al. [17] introduced online matching
in bipartite graphs, in which every vertex has a capacity of 1. The best
competitive ratio of deterministic online algorithms is equal to $1/2$. Karp
et al. proposed a randomized Ranking algorithm that achieves an optimal
competitive ratio of $1-1/e\approx 0.63$. Aggarwal et al. [1] defined online
vertex-weighted bipartite matching and devised a $(1-1/e)$-competitive
algorithm.

Kalyanasundaram and Pruhs [16] investigated the $b$-matching problem if all
servers have equal capacity, i.e. $b_{s}=b$ for all $s\in S$. They presented a
deterministic Balance algorithm that matches a new request to an adjacent
server whose current load is smallest. Balance achieves an optimal competitive
ratio of $1-1/(1+1/b)^{b}$. As $b$ grows, the latter expression tends from
below to $1-1/e$. Grove et al. [13] and Chaudhuri et al. [5] studied
$b$-matchings with a different objective. At any time an algorithm must
maintain a matching between the requests that have arrived so far and the
servers. The goal is to minimize the total number of switches, reassigning
requests to different servers.

The AdWords problem was formally defined by Mehta et al. [20]. They presented
a deterministic online algorithm that achieves a competitive ratio of $1-1/e$,
under the _small-bids assumption_ where the bids are small compared to the
advertisers’ budgets. No randomized algorithm can obtain a better competitive
factor. Buchbinder et al. [4] examined a setting where the degree of each
incoming user is upper bounded by $d$ and gave an algorithm with a competitive
ratio of nearly $1-(1-1/d)^{d}$. Azar et al. [3] showed that this ratio is
best possible, also for randomized algorithms. The expression $1-(1-1/d)^{d}$
is always greater than $1-1/e$ but approaches the latter value as $d$
increases.

The class of $(k,d)$-graphs was defined by Naor and Wajc [21], who studied
online bipartite matching and the AdWords problem. They proposed an algorithm
HighDegree that matches a new request to an available neighbor of highest
current degree. Naor and Wajc proved that HighDegree and generalizations
attain a competitive factor of $1-(1-1/d)^{k}$. This ratio holds for online
bipartite matching and the vertex-weighted extension, where all vertices have
a capacity of 1. Furthermore, it holds for AdWords with equal bids per bidder.
For AdWords with arbitrary bids, the ratio is $(1-R_{\max})(1-(1-1/d)^{k})$,
where $R_{\max}$ is the maximum ratio between the bid of any bidder and its
total budget. Naor and Wajc showed that no deterministic online algorithm for
bipartite matching can achieve a competitive ratio greater than
$1-(1-1/d)^{k}$ if $k\geq d$. For the general AdWords problem, they proved an
upper bound of $(1-R_{\max})(1-(1-1/d)^{k/R_{\max}})$ if $k\geq d$. For
increasing $k/d$, the expression $1-(1-1/d)^{k}$ tends to 1. For $k\approx d$
increasing, it approaches again $1-1/e$.

Cohen and Wajc [6] studied online bipartite matching in $d$-regular graphs and
developed a randomized algorithm with a competitive ratio of $1-O(\sqrt{\log
d/d})$, which tends to 1 as $d$ increases.

Online bipartite matching and the AdWords problem have also been examined in
stochastic input models. A random permutation of the vertices of $R$ may
arrive. Alternatively, the vertices of $R$ are drawn i.i.d. from a known or
unknown distribution. For online bipartite matching, the best online
algorithms currently known achieve competitive ratios of 0.696 and 0.706 [15,
18]. The best possible performance ratios are upper bounded by 0.823 [19], and
hence bounded away from 1. For AdWords, $(1-\varepsilon)$-competitive
algorithms are known, based on the small-bids assumption [9, 10].

Our contributions: We present a comprehensive study of the $b$-matching
problem in $(k,d)$-graphs. Specifically, we develop tight lower and upper
bounds on the performance of deterministic online algorithms. The optimal
competitive ratio tends to 1, for any choice of $k$ and $d$ with $k\geq d$, as
the server capacities increase.

First, in Section 2 we investigate the setting that all servers have the same
capacity, i.e. $b_{s}=b$ for all $s\in S$. We develop an optimal online
algorithm WeightedAssignment via a primal-dual analysis. The resulting
strategy is simple. Associated with each server of current load $l$ and
current degree $\delta$ is a value $V(l,\delta)$. An incoming request is
assigned to an eligible server for which the increment
$V(l,\delta+1)-V(l,\delta)$ is maximized. The values $V(l,\delta)$ can be
calculated in a preprocessing step and retrieved by table lookup when the
requests of $R$ are served. The best values $V(l,\delta)$, for variable $l$
and $\delta$, are determined using recurrence relations. Solving them is non-
trivial because two parameters are involved.

We prove that WeightedAssignment achieves a competitive ratio of $c^{*}$,
where

$c^{*}=1-\frac{1}{b}\left(\sum_{i=1}^{b}i\binom{kb}{b-i}{\frac{1}{(d-1)^{b-i}}}\right)\left(1-\frac{1}{d}\right)^{kb}.$

This is a slightly complex expression, but it is exact in all terms. In
Section 3 we prove that no deterministic online algorithm can attain a
competitive ratio greater than $c^{*}$, for any choices of k and d that
fulfill $k\geq d$.

In Section 4 we consider two generalizations. We assume that each server $s\in
S$ has an individual capacity $b_{s}$ and adapt WeightedAssignment. As for the
competitive factor, in $c^{*}$ the capacity $b$ has to be replaced by
$b_{\min}:=\min_{s\in S}b_{s}$. The resulting competitiveness is again optimal
for $k\geq d$. Furthermore, we study the vertex-weighted problem extension and
again adjust our algorithm. The competitive ratios are identical to those in
the unweighted setting, for uniform and variable server capacities. Our
results also hold for the AdWords problem where bidders issue individual,
equally valued bids.

In Section 5 we analyze the optimal competitive ratio $c^{*}$. We prove that
it tends to 1, for any $k\geq d$, as $b$ increases. Furthermore, we show that
it is strictly increasing in $b$. The analyses are involved and make non-
trivial use of Gauss hypergeometric functions.

A strength of our results is that the optimal competitiveness tends to 1, for
increasing server capacities. Hence almost optimal solutions can be computed
online. For the AdWords problem, high server capacities correspond to the
small-bids assumption. Remarkably, in this setting near-optimal ad allocations
can be computed based on structural properties of the input graph if bidders
issue individual, equally valued bids. Recall that, without degree bounds, the
competitive ratio for the $b$-matching problem tends from below to
$1-1/e\approx 0.63$. The competitiveness of $c^{*}$ improves upon the previous
best ratio of $1-(1-1/d)^{k}$ [21]. The ratio $c^{*}$ is equal to
$1-(1-1/d)^{k}$ for $b=1$ and strictly increasing in $b$, for any $k\geq d$.
Our asymptotic competitiveness of 1 is a significant improvement over
$1-(1-1/d)^{k}\approx 1-1/e^{k/d}$, for the interesting range of small
$k/d\geq 1$. For $k<d$, $1-(1-1/d)^{k}$ and $c^{*}$ can become small. The
algorithms are still $\frac{1}{2}$-competitive since they match requests
whenever possible. We are aware of only two other online matching problems
that admit competitive ratios arbitrarily close to 1. As mentioned above, a
randomized algorithm is known for online matching in $d$-regular unit-capacity
graphs [6]. For the general AdWords problem, respective algorithms exist if
the input $R$ is generated according to probability distributions [9, 10].

##  2 An optimal online algorithm

In this section we study the setting that all servers have a uniform capacity
of $b$. We develop our algorithm WeightedAssignment. While serving requests,
the algorithm maintains a value $V(l_{s},\delta_{s})$, for each server $s$
with load $l_{s}$ and current degree $\delta_{s}$. At any point in time during
the execution of the online algorithm, the load of a server $s$ denotes the
amount of matched edges incident to $s$, while the current degree indicates
the total number of edges incident to $s$. In order to construct the function
$V$ and for the purpose of analysis, we formulate WeightedAssignment as a
primal-dual algorithm. The primal and dual linear programs of the $b$-matching
problem are given at the top of the next page. The primal variables $m(s,r)$
indicate if an edge $\\{s,r\\}\in E$ belongs to the matching. We have dual
variables $x(s)$ and $y(r)$.

In the pseudocode of WeightedAssignment, also shown on this page, Line 7 is
the actual matching step. A new request $r$ is assigned to a neighboring
server $s$ for which the difference
${V(l_{s},\delta_{s}+1)}-V(l_{s},\delta_{s})$ is maximized. $N(r)$ is the set
of adjacent servers with remaining capacity. All other instructions
essentially update primal and dual variables so that a primal and a dual
solution are constructed in parallel.

Observe that no dual variable $y(r)$ of any request $r$ is ever increased by
WeightedAssignment. The dual variable $x(s)$ of a server $s$ can be increased
in Lines 9 and 11. It is increased if $s$ is matched to a neighboring request
$r$ and, importantly, $x(s)$ is also increased if this $r$ is assigned to a
different server.

P: max $\displaystyle\sum_{\\{s,r\\}\in E}m(s,r)$ D: min
$\displaystyle\sum_{s\in S}b\cdot x(s)+\sum_{r\in R}y(r)$ s.t.
$\displaystyle\sum_{r:\\{s,r\\}\in E}m(s,r)\leq b,\ (\forall s\in S)$ s.t.
$\displaystyle x(s)+y(r)\geq 1,\ (\forall\\{s,r\\}\in E)$
$\displaystyle\sum_{s:\\{s,r\\}\in E}m(s,r)\leq 1,\ (\forall r\in R)$
$\displaystyle x(s),\,y(r)\geq 0,\ (\forall s\in S,\forall r\in R)$
$\displaystyle m(s,r)\geq 0,\ (\forall\\{s,r\\}\in E)$

1 Initialize $x(s)=0$, $y(r)=0$ and $m(s,r)=0$, $\forall s\in S$ and $\forall
r\in R$;

2 while  _a new request $r\in R$ arrives_ do

3 Let $N(r)$ denote the set of neighbors $s$ of $r$ with remaining capacity;

4 if  _$N(r)=\emptyset$_ then

5 Do not match $r$;

6 else

7 Match $r$ to $\arg\max\left\\{V(l_{s},\delta_{s}+1)-V(l_{s},\delta_{s}):s\in
N(r)\right\\}$;

8 Update $m(s,r)\leftarrow 1$;

9 Set $x(s)\leftarrow V(l_{s}+1,\delta_{s}+1)$;

10 forall  _$s^{\prime}\neq s\in N(r)$_ do

11 Set $x(s^{\prime})\leftarrow V(l_{s^{\prime}},\delta_{s^{\prime}}+1)$;

12

13 end forall

14

15 end if

16

17 end while

Algorithm 1 WeightedAssignment

In the analysis, we will see how the function $V$ has to be defined so that
WeightedAssignment achieves the desired competitive ratio $c^{*}$. Note that
we always construct a feasible dual solution if $x(s)=1$ holds, for all
servers $s\in S$, by the end of the algorithm. Here lies a crucial idea of the
algorithm and the construction of $V$. We demand $V(b,\delta)=1$, for all
$\delta\geq b$, and $V(l,\delta)=1$ if $\delta\geq kb$, for all $0\leq l\leq
b$. Also, $V(0,0)=0$. These constraints have two important implications.

  1. 1.

The dual variable $x(s)$ of a server $s$ with load $l_{s}$ and degree
$\delta_{s}$ is always equal to $V(l_{s},\delta_{s})$: Consider an incoming
request $r$ that is a neighbor of $s$. While $l_{s}<b$, it holds
$N(r)\neq\emptyset$ and $r$ is matched to some server. Lines 9 and 11
correctly update $x(s)$ with respect to the new load and degree values. If
$l_{s}=b$, then inductively by the first constraint $x(s)=1$ and no update is
necessary.

  2. 2.

The constructed dual solution is feasible: Implication 1 and the second
constraint ensure that ${x(s)=1}$ holds for all $s\in S$ by the end of the
algorithm, since every server $s$ has a degree of at least $kb$.

Let $P$ and $D$ denote the value of the primal and dual solution constructed
by the algorithm, respectively. We denote a change in the value of the primal
and dual solution by $\Delta P$ and $\Delta D$, respectively. It holds that
the size of the matching constructed by WeightedAssignment is exactly
$|\textsc{Alg}|=P$. Moreover, by weak duality, we get that the size of the
optimum matching is $|\textsc{Opt}|\leq D$. Hence, if we were able to bound
$\Delta D\leq\Delta P/c$ at every step, we would obtain a competitive ratio of
$c$.

$\frac{|\textsc{Alg}|}{|\textsc{Opt}|}\geq\frac{P}{D}\geq\frac{P}{\frac{1}{c}\cdot
P}=c\,.$

Recall that the value of the dual solution is only increased if a request $r$
is matched to a server $s$. Then, the value of the primal solution is
increased by 1, while the value of the dual solution is increased by

$\Delta
D=b\cdot\Big{(}V(l_{s}+1,\delta_{s}+1)-V(l_{s},\delta_{s})+\sum_{s^{\prime}\in
N(r)\setminus\\{s\\}}V(l_{s^{\prime}},\delta_{s^{\prime}}+1)-V(l_{s^{\prime}},\delta_{s^{\prime}})\Big{)}\,.$

The algorithm chooses $s$ such that
$V(l_{s},\delta_{s}+1)-V(l_{s},\delta_{s})\geq
V(l_{s^{\prime}},\delta_{s^{\prime}}+1)-V(l_{s^{\prime}},\delta_{s^{\prime}})$
holds for all $s^{\prime}\in N(r)$. Furthermore, $|N(r)|\leq d$ implies that
we can bound this increase by

$\Delta D\leq
b\cdot\Big{(}V(l_{s}+1,\delta_{s}+1)-V(l_{s},\delta_{s})+(d-1)\cdot\big{(}V(l_{s},\delta_{s}+1)-V(l_{s},\delta_{s})\big{)}\Big{)}\,.$

This means, that we need to determine the biggest possible constant
$c^{*}\in(0,1]$ such that

$b\cdot\Big{(}V(l+1,\delta+1)-V(l,\delta)+(d-1)\cdot\big{(}V(l,\delta+1)-V(l,\delta)\big{)}\Big{)}\leq\frac{1}{c^{*}}$
(1)

holds for all $0\leq l<b$ and all $\delta\geq l$, while still satisfying our
constraints that $V(b,\cdot)=1$ and $V(\cdot,\delta^{\prime})=1$ for
$\delta^{\prime}\geq kb$. For this, we define

$p(l,\delta):=V(l+1,\delta+1)-V(l,\delta)\quad\text{and}\quad
q(l,\delta):=V(l,\delta+1)-V(l,\delta)\,.$

In other words, the dual variable $x(s)$ of a server $s$ with load $l$ and
current degree $\delta$ is increased by $p(l,\delta)$, when a request is
assigned to $s$, and increased by $q(l,\delta)$, when a neighboring request is
assigned to a different server. Our constraints immediately give
$p(l,\delta)=q(l,\delta)=0$, if $l=b$ or $\delta\geq kb$. Hence, we will focus
on the case $0\leq l<b$ and $l\leq\delta<kb$ in the following. Rewriting and
rearranging inequality (1) in terms of $p$ and $q$ yields

$q(l,\delta)\leq\frac{1}{d-1}\left(\frac{1}{b\cdot c}-p(l,\delta)\right)\,.$

We treat the values $p(i,i)$, for $0\leq i<b-1$, as the variables of our
optimization, since every other $p$ and $q$ value can then be computed based
on these choices. To get comfortable with the recursions and ideas in the
latter part of this section, we do the following warm-up, where we consider
$V(b-1,\delta)$. It holds

$V(b-1,\delta)=\sum_{i=0}^{b-2}p(i,i)+\sum_{j=b-1}^{\delta-1}q(b-1,j)\,.$

Our first constraint $V(b,\delta)=1$, for all $\delta\geq b$, implies that
$p(b-1,\delta)=1-V(b-1,\delta)$. We do not want to waste any potential
increases in our dual variables, since we want to maximize $c$. Thus, we will
choose the maximum possible value for $q(b-1,\delta)$, which is

$q(b-1,\delta)=\frac{1}{d-1}\left(\frac{1}{b\cdot
c}-p(b-1,\delta)\right)=\frac{1}{d-1}\left(\frac{1}{b\cdot
c}-1+V(b-1,\delta)\right)\,.$

It follows that

$V(b-1,\delta+1)=V(b-1,\delta)+q(b-1,\delta)=\frac{d}{d-1}V(b-1,\delta)+\frac{1}{d-1}\left(\frac{1}{b\cdot
c}-1\right)\,,$ (2)

for all $b-1\leq\delta<kb$ and with $V(b-1,b-1)=\sum_{i=0}^{b-2}p(i,i)$. To
ease notation in the future, we further define
$P_{i}:=\sum_{j=0}^{i-1}p(j,j)$, for all $0\leq i\leq b-1$, so that we get
$P_{i}=V(i,i)$. Note that $P_{0}=0$. Solving the recurrence relation (2)
yields

$\displaystyle V(b-1,\delta)$
$\displaystyle=\left(\frac{d}{d-1}\right)^{\delta-(b-1)}P_{b-1}+\frac{1}{d-1}\left(\frac{1}{b\cdot
c}-1\right)\cdot\sum_{i=0}^{\delta-(b-1)-1}\left(\frac{d}{d-1}\right)^{i}$
$\displaystyle=\left(\frac{d}{d-1}\right)^{\delta-(b-1)}P_{b-1}+\frac{1}{d-1}\left(\frac{1}{b\cdot
c}-1\right)\cdot\frac{\left(\frac{d}{d-1}\right)^{\delta-(b-1)}-1}{\left(\frac{d}{d-1}\right)-1}$
$\displaystyle=\left(\frac{d}{d-1}\right)^{\delta-(b-1)}\left(P_{b-1}+\frac{1}{b\cdot
c}-1\right)+1-\frac{1}{b\cdot c}\,.$

The following lemma generalizes the computation above to all other load
levels.

######  Lemma 1.

For all $l$, $0\leq l\leq b$, and for all $\delta$, $l\leq\delta\leq kb$, it
holds that

$V(l,\delta)=\sum_{i=l}^{b-1}(-1)^{i-l}\frac{1}{(d-1)^{i-l}}\binom{\delta-l}{i-l}\left(\frac{d}{d-1}\right)^{\delta-i}\left(P_{i}+\frac{b-i}{b\cdot
c}-1\right)+1-\frac{b-l}{b\cdot c}\,.$ (3)

###### Proof.

By induction over $l$, starting with $l=b$ and going down to $l=0$. The
induction base $l=b$ is true, because we have $V(b,\delta)=1$. Thus, we focus
on the induction step $l+1\leadsto l$. Similar arguments as before yield for
$l\leq\delta<kb$

$q(l,\delta)=\frac{1}{d-1}\left(\frac{1}{b\cdot
c}-p(l,\delta)\right)=\frac{1}{d-1}\left(\frac{1}{b\cdot
c}-V(l+1,\delta+1)+V(l,\delta)\right)\,.$

We can now define the recurrence relation for $V(l,\delta)$

$\displaystyle
V(l,\delta+1)=V(l,\delta)+q(l,\delta)=\frac{d}{d-1}V(l,\delta)+\frac{1}{d-1}\left(\frac{1}{b\cdot
c}-V(l+1,\delta+1)\right)\,,$

with $V(l,l)=P_{l}$. Solving this recurrence yields

$\displaystyle V(l,\delta)=$
$\displaystyle\left(\frac{d}{d-1}\right)^{\delta-l}P_{l}+\frac{1}{d-1}\frac{1}{b\cdot
c}\sum_{i=0}^{\delta-l-1}\left(\frac{d}{d-1}\right)^{i}-\frac{1}{d-1}\sum_{i=0}^{\delta-l-1}\left(\frac{d}{d-1}\right)^{i}V(l+1,\delta-i)\,.$
(4)

In the next step, we will need the following fact [12].

######  Fact 1.

For $n,k\in\mathbb{N}_{0}$, it holds that

$\sum_{i=0}^{n}\binom{i}{k}=\binom{n+1}{k+1}\,.$

Next, we apply the induction hypothesis to determine $V(l,\delta)$. For
clarity, we focus on the last sum of equality (4) first

$\displaystyle\sum_{i=0}^{\delta-l-1}\left(\frac{d}{d-1}\right)^{i}V(l+1,\delta-i)\overset{\text{IH}}{=}\sum_{i=0}^{\delta-l-1}\left(\frac{d}{d-1}\right)^{i}\left[\sum_{j=l+1}^{{b}-1}(-1)^{j-(l+1)}\frac{1}{(d-1)^{j-(l+1)}}\right.$
$\displaystyle\left.\quad\cdot\,\binom{\delta-i-(l+1)}{j-(l+1)}\left(\frac{d}{d-1}\right)^{\delta-
i-j}\left(P_{j}+\frac{{b}-j}{b\cdot c}-1\right)+1-\frac{{b}-(l+1)}{b\cdot
c}\right]$
$\displaystyle=\sum_{j=l+1}^{{b}-1}(-1)^{j-(l+1)}\frac{1}{(d-1)^{j-(l+1)}}\left(\frac{d}{d-1}\right)^{\delta-j}\left(P_{j}+\frac{{b}-j}{b\cdot
c}-1\right)\sum_{i=0}^{\delta-l-1}\binom{\delta-i-(l+1)}{j-(l+1)}$
$\displaystyle\quad+\left(1-\frac{{b}-(l+1)}{b\cdot
c}\right)\sum_{i=0}^{\delta-l-1}\left(\frac{d}{d-1}\right)^{i}$
$\displaystyle=\sum_{j=l+1}^{{b}-1}(-1)^{j-(l+1)}\frac{1}{(d-1)^{j-(l+1)}}\left(\frac{d}{d-1}\right)^{\delta-j}\left(P_{j}+\frac{{b}-j}{b\cdot
c}-1\right)\sum_{i=0}^{\delta-l-1}\binom{i}{j-(l+1)}$
$\displaystyle\quad+\left(1-\frac{b-(l+1)}{b\cdot
c}\right)(d-1)\left(\left(\frac{d}{d-1}\right)^{\delta-l}-1\right)$
$\displaystyle=\sum_{j=l+1}^{b-1}(-1)^{j-(l+1)}\frac{1}{(d-1)^{j-(l+1)}}\left(\frac{d}{d-1}\right)^{\delta-j}\left(P_{j}+\frac{{b}-j}{b\cdot
c}-1\right)\binom{\delta-l}{j-l}$
$\displaystyle\quad+\left(1-\frac{b-(l+1)}{b\cdot
c}\right)(d-1)\left(\left(\frac{d}{d-1}\right)^{\delta-l}-1\right)\,,$

where we used Fact 1 in the last step. Now, we can finish the induction step
by plugging this into (4)

$\displaystyle V(l,\delta)$
$\displaystyle=\left(\frac{d}{d-1}\right)^{\delta-l}P_{l}+\frac{1}{b\cdot
c}\left(\left(\frac{d}{d-1}\right)^{\delta-l}-1\right)-\left(1-\frac{b-(l+1)}{b\cdot
c}\right)\left(\left(\frac{d}{d-1}\right)^{\delta-l}-1\right)$
$\displaystyle\quad+\sum_{j=l+1}^{b-1}(-1)^{j-l}\frac{1}{(d-1)^{j-l}}\left(\frac{d}{d-1}\right)^{\delta-j}\left(P_{j}+\frac{{b}-j}{b\cdot
c}-1\right)\binom{\delta-l}{j-l}$
$\displaystyle=\left(\frac{d}{d-1}\right)^{\delta-l}\left(P_{l}+\frac{1}{b\cdot
c}+\frac{b-(l+1)}{b\cdot c}-1\right)+1-\frac{1}{b\cdot
c}-\frac{b-(l+1)}{b\cdot c}$
$\displaystyle\quad+\sum_{j=l+1}^{b-1}(-1)^{j-l}\frac{1}{(d-1)^{j-l}}\left(\frac{d}{d-1}\right)^{\delta-j}\left(P_{j}+\frac{{b}-j}{b\cdot
c}-1\right)\binom{\delta-l}{j-l}$
$\displaystyle=\sum_{j=l}^{b-1}(-1)^{j-l}\frac{1}{(d-1)^{j-l}}\left(\frac{d}{d-1}\right)^{\delta-j}\left(P_{j}+\frac{{b}-j}{b\cdot
c}-1\right)\binom{\delta-l}{j-l}+1-\frac{b-l}{b\cdot c}\,.\qed$

So far, we have only leveraged our constraint $V(b,\cdot)=1$. With our
description of $V(l,\delta)$, for all $0\leq l\leq b$ and $l\leq\delta\leq
kb$, we can also leverage $V(\cdot,kb)=1$ to determine $P_{i}$, for all $0\leq
i\leq b-1$. For this, we will need the following technical lemma.

######  Lemma 2.

For $k,n,m\in\mathbb{N}$, with $m\geq n\geq k$, it holds that

$\displaystyle\sum_{i=1}^{n-k}(-1)^{i}\binom{m}{i}\binom{m-i}{n-k-i}=-\binom{m}{n-k}\,.$

###### Proof.

Observe that

$\displaystyle\binom{m}{i}\binom{m-i}{n-k-i}$
$\displaystyle=\frac{m!}{(m-i)!i!}\cdot\frac{(m-i)!}{(m-(n-k))!(n-k-i)!}$
$\displaystyle=\frac{(n-k)!}{(n-k-i)!i!}\cdot\frac{m!}{(m-(n-k))!(n-k)!}=\binom{n-k}{i}\binom{m}{n-k}\,.$

Next, notice that the binomial expansion implies that

$0=(1-1)^{n-k}=\sum_{i=0}^{n-k}\binom{n-k}{i}(-1)^{i}\,.$

Hence, we can conclude

$\displaystyle\sum_{i=1}^{n-k}(-1)^{i}\binom{m}{i}\binom{m-i}{n-k-i}$
$\displaystyle=\binom{m}{n-k}\sum_{i=1}^{n-k}(-1)^{i}\binom{n-k}{i}$
$\displaystyle=\binom{m}{n-k}\left(\sum_{i=0}^{n-k}(-1)^{i}\binom{n-k}{i}-1\right)$
$\displaystyle=\binom{m}{n-k}(0-1)=-\binom{m}{n-k}\,.\qed$

######  Lemma 3.

For all $l$, $0\leq l\leq b-1$, it holds that

$\left(\frac{d}{d-1}\right)^{kb-l}\left(P_{l}+\frac{b-l}{b\cdot
c}-1\right)=\frac{1}{b\cdot
c}\left(\sum_{i=1}^{b-l}i\binom{kb-l}{b-l-i}\frac{1}{(d-1)^{b-l-i}}\right)\,.$
(5)

###### Proof.

By induction over $l$ from $l=b-1$ down to $l=0$. We start with the induction
base $l=b-1$. Our second constrain yields $V(b-1,kb)=1$. It then follows from
Lemma 1 that

$\displaystyle
V(b-1,kb)=\left(\frac{d}{d-1}\right)^{kb-(b-1)}\left(P_{b-1}+\frac{1}{b\cdot
c}-1\right)+1-\frac{1}{b\cdot c}\overset{\text{def.}}{=}1\,,$

which immediately finishes the induction base, since the right-hand side of
(5) is simply $1/(b\cdot c)$.

We can now move on to the induction step $\forall i>l\leadsto l$. We use
$V(l,kb)=1$ and rearrange with the help of Lemma 1

$\displaystyle\left(\frac{d}{d-1}\right)^{kb-l}\left(P_{l}+\frac{b-l}{b\cdot
c}-1\right)=\frac{b-l}{b\cdot c}$ (6)
$\displaystyle\quad-\sum_{i=l+1}^{b-1}(-1)^{i-l}\frac{1}{(d-1)^{i-l}}\binom{kb-l}{i-l}\left(\frac{d}{d-1}\right)^{kb-i}\left(P_{i}+\frac{b-i}{b\cdot
c}-1\right)\,.$

It is now possible to apply the induction hypothesis. For clarity, we focus on
the second line of (6)

$\displaystyle\sum_{i=l+1}^{b-1}(-1)^{i-l}\frac{1}{(d-1)^{i-l}}\binom{kb-l}{i-l}\frac{1}{b\cdot
c}\left(\sum_{j=1}^{b-i}j\binom{kb-i}{b-i-j}\frac{1}{(d-1)^{b-i-j}}\right)$
$\displaystyle=\frac{1}{b\cdot
c}\left(\sum_{a=1}^{b-l-1}(-1)^{a}\sum_{j=1}^{b-(l+a)}j\frac{1}{(d-1)^{b-l-j}}\binom{kb-l}{a}\binom{kb-(l+a)}{b-(l+a)-j}\right)\,,$

where we substituted $a:=i-l$. Next, we carefully swap these nested sums. For
this, observe that, for a fixed value $j$, we have exactly $b-l-j$ addends,
more precisely, one addend for each $1\leq a\leq b-l-j$

$\displaystyle\frac{1}{b\cdot
c}\left(\sum_{a=1}^{b-l-1}(-1)^{a}\sum_{j=1}^{b-(l+a)}j\frac{1}{(d-1)^{b-l-j}}\binom{kb-l}{a}\binom{kb-
l-a}{b-l-a-j}\right)$ $\displaystyle=\frac{1}{b\cdot
c}\left(\sum_{j=1}^{b-l-1}j\frac{1}{(d-1)^{b-l-j}}\sum_{a=1}^{b-l-j}(-1)^{a}\binom{kb-l}{a}\binom{kb-
l-a}{b-l-a-j}\right)$ $\displaystyle=-\frac{1}{b\cdot
c}\left(\sum_{j=1}^{b-l-1}j\frac{1}{(d-1)^{b-l-j}}\binom{kb-l}{b-l-j}\right)\,,$

where we applied Lemma 2 with $k=j$, $n=b-l$ and $m=kb-l$ in the last step.
Plugging this back into (6) gives

$\displaystyle\left(\frac{d}{d-1}\right)^{kb-l}\left(P_{l}+\frac{b-l}{b\cdot
c}-1\right)$ $\displaystyle=\frac{b-l}{b\cdot c}+\frac{1}{b\cdot
c}\left(\sum_{j=1}^{b-l-1}j\frac{1}{(d-1)^{b-l-j}}\binom{kb-l}{b-l-j}\right)$
$\displaystyle=\frac{1}{b\cdot
c}\left(\sum_{j=1}^{b-l}j\frac{1}{(d-1)^{b-l-j}}\binom{kb-l}{b-l-j}\right)\,.\qed$

With the help of Lemma 3, we can finally determine the resulting constant
$c^{*}$. For $l=0$, we have $P_{0}=0$, and thus

$\left(\frac{d}{d-1}\right)^{kb}\left(\frac{1}{c^{*}}-1\right)=\frac{1}{b\cdot
c^{*}}\left(\sum_{i=1}^{b}i\binom{kb}{b-i}\frac{1}{(d-1)^{b-i}}\right)\,,$

where solving for $c^{*}$ yields

$c^{*}=1-\frac{1}{b}\left(\sum_{i=1}^{b}i\binom{kb}{b-i}\frac{1}{(d-1)^{b-i}}\right)\left(1-\frac{1}{d}\right)^{kb}\,.$

######  Theorem 1.

WeightedAssignment achieves a competitive ratio of $c^{*}$ for the online
$b$-matching problem with uniform server capacities on $(k,d)$-graphs.

01234567801234$l$$\delta$016376393125157189221485975971251571892211011071171331571892211591611651731892212212212212212211621263032323232484338343232323211162228323232534842363232326101624323258544840323224816326260564832
Figure 1: The function $V$ for $k=d=2$ and $b=4$. All values are multiplied by
$221$.

Lemma 1, together with Lemma 3 and $c^{*}$, specifies the function $V$. Its
values can be calculated in a preprocessing step and accessed by table lookup
when WeightedAssignment serves requests. The parameters $k$ and $d$ must be
known. In an application, they can be learned over time. Alternatively, one
can work with conservative estimates. Figure 1 shows the function $V$ for a
small example with $k=d=2$ and $b=4$. In this case, we have $c^{*}=221/256$
and $1/(bc^{*})=64/221$. The arrows depict the possible increases in $V$ for
every $l$, $0\leq l<b$, and $\delta$, $l\leq\delta<kb$, i.e. horizontal arrows
denote the $q(l,\delta)$ values and diagonal arrows the $p(l,\delta)$ values.
All actual values are multiplied by $221$ in order to eliminate fractions.
Observe that $p(l,\delta)+(d-1)q(l,\delta)=1/(bc^{*})$ holds for all $l$ and
$\delta$. This is what allows us to bound the total increase in the dual
solution by $1/c^{*}$, if we always pick the neighboring server $s$ that
maximizes $q(l_{s},\delta_{s})$. For the matching decisions,
WeightedAssignment only uses the horizontal arrows. Notice that
WeightedAssignment is different from a Balance algorithm that breaks ties by
HighDegree, or from a HighDegree algorithm that breaks ties by Balance. For
example, WeightedAssignment prefers a server with load $1$ and degree $5$ to a
server with load $0$ and degree $1$, whom it then prefers to a server with
load $3$ and degree $6$.

##  3 Upper bounds

We will show that WeightedAssignment is optimal for $(k,d)$-graphs with $k\geq
d$, i.e. no deterministic online algorithm can achieve a competitive ratio
better than $c^{*}$. We start by proving this for the online $b$-matching
problem with uniform server capacities, and later extend it to the more
general problems.

First, we show that any ($k,d$)-graph with uniform server capacities $b$ has a
perfect $b$-matching, i.e. a matching where every server $s\in S$ is matched
exactly $b$ times, if $k\geq d$. This generalizes Lemma 6.1 in [21], which
states this for $b=1$.

######  Lemma 4.

Every ($k,d$)-graph $G=(S\cup R,E)$, where $k\geq d$, with uniform server
capacities $b$ has a perfect $b$-matching.

###### Proof.

We perform the known reduction of the $b$-matching problem to the classical
maximum matching problem, i.e. we replace every server with capacity $b$ by
$b$ unit servers having the same adjacent requests as the replaced server.
This will result in a $(kb,db)$-graph without capacities, where $kb\geq db$.
Lemma 6.1 in [21] then implies that there exists a perfect matching in this
graph, which in turn implies the existence of a perfect $b$-matching in the
original graph. ∎

We move on to describing the adversary input. We start by following the
construction of the previously known upper bound detailed in [21]. There are
$N=d^{kb}$ servers, and the requests arrive in $kb$ rounds. Let $S_{i}$ denote
the set of unmatched servers at the beginning of round $i$, $0\leq i<kb$. It
will hold that every server in $S_{i}$ has a current degree of $i$ and that
$|S_{i}|=N(1-1/d)^{i}$. Note that this number is always a multiple of $d$, by
choice of $N$. During round $i$, $|S_{i}|/d$ requests are introduced, such
that every request is adjacent to exactly $d$ distinct servers in $S_{i}$ and
every server in $S_{i}$ gains one new neighboring request. If the online
algorithm decides not to match an introduced request, we consider it matched
to an arbitrary neighbor. This will only improve the performance of said
algorithm. This means that a $(1-1/d)$ fraction of the servers in $S_{i}$ are
still unmatched after round $i$, explaining the previously mentioned
$S_{i}=N(1-1/d)^{i}$. Thus, there are $N\cdot(1-1/d)^{kb}$ servers with degree
$kb$ and load $0$ after round $kb-1$, irrespective of what choices the
algorithm makes. In a final round, further requests are introduced to all
matched servers arbitrarily, such that we get a valid $(k,d)$-graph. The
online algorithm will have matched at most
$bN\cdot\left(1-(1-1/d)^{kb}\right)$ requests, while Lemma 4 implies that an
optimal offline algorithm matches $bN$ requests. This yields the previously
known upper bound of $\left(1-(1-1/d)^{kb}\right)$.

However, it seems suboptimal to introduce requests arbitrarily after the
initial $kb$ rounds. In fact, we will show that we can further limit the
number of requests matched by the online algorithm if we introduce the
requests more carefully. Note that all the servers that are matched during
round $i$ of the previous input are similar in the sense that they all have
degree $i$ and load $1$. We will apply the ideas above recursively to the sets
of matched servers of all rounds. More precisely, let $T$ denote the set of
matched server during some round. Say all servers in $T$ have load $l$, $0\leq
l<b$, and degree $\delta$, $l\leq\delta<kb$. We then schedule $kb-\delta$
rounds for $T$ using the same construction as above. Let $T_{j}$ denote the
set of servers that still have load $l$ at the beginning of round $j$, $0\leq
j<kb-\delta$. It will now hold that every server in $T_{j}$ has a current
degree of $\delta+j$ and that $|T_{i}|=|T|(1-1/d)^{i}$. We have to make sure
that all the possible values of $|T_{i}|$ are multiples of $d$. This is done
by increasing the initial number of servers $N$ adequately. After these
$kb-\delta$ round, we have $|T|\cdot(1-1/d)^{kb-\delta}$ servers with degree
$kb$ and load $l$. This process is repeated for all the sets of matched
servers until we eventually obtain a valid $(k,d)$-graph, in which every
server has degree $kb$.

For this, we formally define a function $F$, where $F(x,l,\delta)$ denotes how
many units of capacity we can force a deterministic online algorithm to leave
empty when starting with $x$ servers that all have load $l$ and degree
$\delta$. This allows us to upper bound the number of matched requests by
$bN-F(N,0,0)$, yielding the following upper bound

$c\leq\frac{bN-F(N,0,0)}{bN}=1-\frac{F(N,0,0)}{bN}\,.$ (7)

We cannot create any empty spots on full servers, so we have
$F(x,b,\delta)=0$, for all $b\leq\delta\leq kb$. Once a server has $kb$
adjacent requests, we have satisfied the $(k,d)$-graph property locally, so we
do not need to introduce any more adjacent requests for this server. This is
captured by $F(x,l,kb)=x\cdot(b-l)$, for all $0\leq l\leq b$. For all other
combinations of $l$ and $\delta$, it is possible to define $F$ recursively.
Recall that we introduce $kb-\delta$ rounds when starting with $x$ servers all
with load $l$ and degree $\delta$. During each of these rounds, exactly a
$1/d$ fraction of the servers that still had load $l$ at the start of the
round are discarded. Moreover, every server gets exactly one new neighbor
during each round until they are matched. This implies

$F(x,l,\delta)=x\cdot\left(1-\frac{1}{d}\right)^{kb-\delta}(b-l)+\sum_{i=1}^{kb-\delta}F\left(x\cdot\frac{1}{d}\left(1-\frac{1}{d}\right)^{i-1},l+1,\delta+i\right)\,,$
(8)

for all $0\leq l<b$ and $l\leq\delta<kb$. The following lemma solves this
recurrence, which we can then apply in (7) to obtain the theorem.

######  Lemma 5.

For all $l$, $0\leq l\leq b$, and all $\delta$, $l\leq\delta\leq kb$, it holds
that

$F(x,l,\delta)=x\left(1-\frac{1}{d}\right)^{kb-\delta}\left(\sum_{i=1}^{b-l}i\binom{kb-\delta}{b-l-i}\frac{1}{(d-1)^{b-l-i}}\right)\,.$
(9)

###### Proof.

By induction over $l$, starting with $l=b$ and going down to $l=0$. The
induction base is satisfied as we get the empty sum in (9), making the whole
expression zero. In the induction step $l+1\leadsto l$, we can apply our
induction hypothesis to $F$ in (8).

$\displaystyle\sum_{i=1}^{kb-\delta}F\left(x\cdot\frac{1}{d}\left(1-\frac{1}{d}\right)^{i-1},l+1,\delta+i\right)$
$\displaystyle\overset{\text{IH}}{=}\sum_{i=1}^{kb-\delta}x\frac{1}{d}\left(1-\frac{1}{d}\right)^{i-1}\left(1-\frac{1}{d}\right)^{kb-(\delta+i)}\left(\sum_{j=1}^{b-(l+1)}j\binom{kb-\delta-i}{b-(l+1)-j}\frac{1}{(d-1)^{b-(l+1)-j}}\right)$
$\displaystyle=x\frac{1}{d}\left(1-\frac{1}{d}\right)^{kb-\delta-1}\left(\sum_{j=1}^{b-(l+1)}j\frac{1}{(d-1)^{b-(l+1)-j}}\sum_{i=1}^{kb-\delta}\binom{kb-\delta-i}{b-(l+1)-j}\right)$
$\displaystyle=x\left(1-\frac{1}{d}\right)^{kb-\delta}\frac{1}{d-1}\left(\sum_{j=1}^{b-(l+1)}j\frac{1}{(d-1)^{b-l-j-1}}\sum_{i=0}^{kb-\delta-1}\binom{i}{b-l-j-1}\right)$
$\displaystyle=x\left(1-\frac{1}{d}\right)^{kb-\delta}\left(\sum_{j=1}^{b-(l+1)}j\frac{1}{(d-1)^{b-l-j}}\binom{kb-\delta}{b-l-j}\right)\,,$

where we used Fact 1 in the last step. Finally, we can plug this result back
into (8) to obtain

$\displaystyle F(x,l,\delta)$
$\displaystyle=x\cdot\left(1-\frac{1}{d}\right)^{kb-\delta}(b-l)+\sum_{i=1}^{kb-\delta}F\left(x\cdot\frac{1}{d}\left(1-\frac{1}{d}\right)^{i-1},l+1,\delta+i\right)$
$\displaystyle=x\cdot\left(1-\frac{1}{d}\right)^{kb-\delta}\left((b-l)+\sum_{j=1}^{b-(l+1)}j\frac{1}{(d-1)^{b-l-j}}\binom{kb-\delta}{b-l-j}\right)$
$\displaystyle=x\cdot\left(1-\frac{1}{d}\right)^{kb-\delta}\left(\sum_{j=1}^{b-l}j\frac{1}{(d-1)^{b-l-j}}\binom{kb-\delta}{b-l-j}\right)\,.\qed$

######  Theorem 2.

No deterministic online algorithm for the $b$-matching problem with uniform
server capacities $b$ can achieve a competitiveness better than $c^{*}$ on
$(k,d)$-graphs with $k\geq d$.

We extend this upper bound to the more general case with variable server
capacities, which we will examine in the next section. Let $b_{min}=\min_{s\in
S}b_{s}$. The optimal competitiveness is then

$c^{*}_{\min}=1-\frac{1}{b_{\min}}\left(\sum_{i=1}^{b_{\min}}i\binom{kb_{\min}}{b_{\min}-i}\frac{1}{(d-1)^{b_{\min}-i}}\right)\left(1-\frac{1}{d}\right)^{kb_{\min}}\,.$

######  Corollary 1.

No deterministic online algorithm for the $b$-matching problem with variable
server capacities can achieve a competitive ratio better than $c^{*}_{\min}$
on $(k,d)$-graphs with $k\geq d$.

###### Proof.

Note that we can upscale the number of initial servers $N$ and thus the number
of matched requests in the adversary input for uniform server capacities. This
means that for any set of server capacities $B$ (with $|B|<\infty$), we can
create the adversary input with $N$ servers for the capacity $b^{\prime}$
which minimizes the corresponding competitive ratio $c^{*}$. Moreover, we only
create one server for every capacity in $B\setminus\\{b^{\prime}\\}$ and add
enough neighbors that are only adjacent to the respective server such that we
obtain a valid $(k,d)$-graph. Even though this will increase the number of
matched requests by $\sum_{b\in B\setminus\\{b^{\prime}\\}}b$, this increase
can be made null by increasing $N$ sufficiently. In the limit, any
deterministic online algorithm achieves a competitive ratio of $\min_{s\in
S}c^{*}_{s}$. In Section 5, we show that $c^{*}$ is strictly increasing in $b$
if $k\geq d$, implying that $\min_{s\in S}c^{*}_{s}=c^{*}_{\min}$. ∎

Obviously, Theorem 2 and Corollary 1 also hold for the more general vertex-
weighted $b$-matching problem, addressed in the next section.

##  4 Variable server capacities and vertex weights

We detail the necessary changes to WeightedAssignment such that it can handle
variable server capacities as well as vertex weights, while still achieving
the optimal competitive ratio.

Variable server capacities: Recall that every server $s\in S$ now has a server
capacity $b_{s}$, and thus a degree of at least $d(s)\geq k\cdot b_{s}$. This
changes the objective function of the dual linear program to

$\sum_{s\in S}b_{s}\cdot x(s)+\sum_{r\in R}y(r)\,.$

We handle this by computing the function $V_{s}$ for every server
individually, for its capacity $b_{s}$. This means that we construct $V_{s}$
according to Section 2, such that

$b_{s}\cdot\Big{(}V_{s}(l+1,\delta+1)-V_{s}(l,\delta)+(d-1)\cdot\big{(}V_{s}(l,\delta+1)-V_{s}(l,\delta)\big{)}\Big{)}\leq\frac{1}{c^{*}_{s}}\,,$
(10)

where $c^{*}_{s}$ is equal to $c^{*}$, but $b$ is replaced by $b_{s}$.
Moreover, we have $V_{s}(b_{s},\cdot)=1$ and $V_{s}(\cdot,\delta^{\prime})=1$
if $\delta^{\prime}\geq kb_{s}$, meaning that we again construct a feasible
dual solution. However, we still have to adapt the decision criterion of
WeightedAssignment. We change Line 7 in Algorithm 1 to

$\text{Match $r$ to
}\arg\max\left\\{b_{s}\cdot\big{(}V_{s}(l_{s},\delta_{s}+1)-V_{s}(l_{s},\delta_{s})\big{)}:s\in
N(r)\right\\}\,.$

This allows us to upper bound the total increase in the dual solution when the
adapted strategy, called WeightedAssignment(VC), assigns a request $r$ to a
server $s$ by

$\displaystyle\Delta D$
$\displaystyle=b_{s}\cdot\Big{(}V_{s}(l_{s}+1,\delta_{s}+1)-V_{s}(l_{s},\delta_{s})\Big{)}+\sum_{s^{\prime}\in
N(r)\setminus\\{s\\}}b_{s^{\prime}}\cdot\Big{(}V_{s^{\prime}}(l_{s^{\prime}},\delta_{s^{\prime}}+1)-V_{s^{\prime}}(l_{s^{\prime}},\delta_{s^{\prime}})\Big{)}$
$\displaystyle\leq
b_{s}\cdot\Big{(}V_{s}(l_{s}+1,\delta_{s}+1)-V_{s}(l_{s},\delta_{s})+(d-1)\cdot\big{(}V_{s}(l_{s},\delta_{s}+1)-V_{s}(l_{s},\delta_{s})\big{)}\Big{)}\leq\frac{1}{c^{*}_{s}}\,.$

Thus, WeightedAssignment(VC) achieves a competitive ratio of $\min_{s\in
S}c^{*}_{s}$. In Section 5 we will show that $c^{*}$ is monotonically
increasing in $b$ for $k\geq d$, meaning that $\min_{s\in
S}c^{*}_{s}=c^{*}_{\min}$, cf. Section 3.

######  Theorem 3.

WeightedAssignment(VC) achieves a competitive ratio of $\min_{s\in
S}c^{*}_{s}$ the $b$-matching problem with variable server capacities on
$(k,d)$-graphs. The ratio equals $c^{*}_{\min}$ and is optimal for $k\geq d$.

Vertex weights: At last, we consider the vertex-weighted extension of the
online $b$-matching problem. Every server $s\in S$ now has a weight $w_{s}$
assigned to it, and the value of every matching edge incident to $s$ is
multiplied by $w_{s}$. This problem is modelled by the following linear
programs.

P: max $\displaystyle\sum_{\\{s,r\\}\in E}w_{s}\cdot m(s,r)$ D: min
$\displaystyle\sum_{s\in S}w_{s}\cdot b_{s}\cdot x(s)+\sum_{r\in R}y(r)$ s.t.
$\displaystyle\sum_{r:\\{s,r\\}\in E}w_{s}\cdot m(s,r)\leq w_{s}\cdot b_{s},\
(\forall s\in S)$ s.t. $\displaystyle w_{s}\cdot x(s)+y(r)\geq w_{s},\
(\forall\\{s,r\\}\in E)$ $\displaystyle\sum_{s:\\{s,r\\}\in E}m(s,r)\leq 1,\
(\forall r\in R)$ $\displaystyle x(s),\,y(r)\geq 0,\ (\forall s\in S,\forall
r\in R)$ $\displaystyle m(s,r)\geq 0,\ (\forall\\{s,r\\}\in E)$

Observe that $x(s)=1$, for all $s\in S$, by the end of the algorithm still
implies dual feasibility. Hence, we do not need to change the construction of
$V_{s}$, and still obtain a feasible dual solution. All we need to do is to
change the decision criterion of WeightedAssignment(VC) once more to

$\text{Match $r$ to }\arg\max\left\\{w_{s}\cdot
b_{s}\cdot\big{(}V_{s}(l_{s},\delta_{s}+1)-V_{s}(l_{s},\delta_{s})\big{)}:s\in
N(r)\right\\}\,.$

Whenever the resulting algorithm WeightedAssignment(VW) assigns a request $r$
to a server $s$, we increase the primal solution by $w_{s}$, while we can
upper bound the increase in the dual solution by

$\displaystyle\Delta D$ $\displaystyle\leq w_{s}\cdot
b_{s}\cdot\Big{(}V_{s}(l_{s}+1,\delta_{s}+1)-V_{s}(l_{s},\delta_{s})+(d-1)\cdot\big{(}V_{s}(l_{s},\delta_{s}+1)-V_{s}(l_{s},\delta_{s})\big{)}\Big{)}\leq\frac{w_{s}}{c^{*}_{s}}\,.$

This again yields a competitiveness of $\min_{s\in S}c^{*}_{s}$.

######  Theorem 4.

WeightedAssignment(VW) achieves a competitive ratio of $\min_{s\in
S}c^{*}_{s}$ for the vertex-weighted $b$-matching problem with variable server
capacities on $(k,d)$-graphs. The ratio equals $c^{*}_{\min}$ and is optimal
for $k\geq d$.

##  5 Analysis of the competitive ratio

######  Theorem 5.

If $k\geq d\geq 2$, the competitive ratio $c^{*}$ converges to one as $b$
tends to infinity, that is $\lim_{b\rightarrow\infty}c^{*}=1$.

###### Proof.

We show that

$\lim_{b\rightarrow\infty}\frac{1}{b}\left(\sum_{i=1}^{b}i\binom{kb}{b-i}\frac{1}{(d-1)^{b-i}}\right)\left(1-\frac{1}{d}\right)^{kb}=0\,,$

for all $k,d\in\mathbb{N}$ with $k\geq d\geq 2$. As a first step, we prove

$\frac{1}{b}\left(\sum_{i=1}^{b}i\binom{kb}{b-i}\frac{1}{(d-1)^{b-i}}\right)\leq\binom{kb}{b-1}\frac{1}{(d-1)^{b-1}}\,.$
(11)

For this, observe that

$\binom{n}{k}=\binom{n}{k-i}\prod_{j=1}^{i}\frac{n-k+j}{k+1-j}\,,$

which means

$\displaystyle\sum_{i=1}^{b}i\binom{kb}{b-i}\frac{1}{(d-1)^{b-i}}$
$\displaystyle=\binom{kb}{b-1}\frac{1}{(d-1)^{b-1}}\sum_{i=1}^{b}i(d-1)^{i-1}\prod_{j=1}^{i-1}\frac{b-j}{kb-(b-1)+j}\,.$
(12)

In order to accurately bound the sum above, we rely on the theory of
_hypergeometric functions_.

######  Definition 1.

A Gauss hypergeometric function ${}_{2}F_{1}(\alpha,\beta;\gamma;z)$ can be
defined as

${}_{2}F_{1}(\alpha,\beta;\gamma;z)=1+\frac{\alpha\cdot\beta}{\gamma\cdot
1}z+\frac{\alpha(\alpha+1)\cdot\beta(\beta+1)}{\gamma(\gamma+1)\cdot 1\cdot
2}z^{2}+\ldots=\sum_{n=0}^{\infty}\frac{(\alpha)_{n}(\beta)_{n}}{(\gamma)_{n}}\frac{z^{n}}{n!}\,,$

where $\alpha,\beta,\gamma$ are parameters and $z$ is the variable. Here,
$(x)_{n}$ denotes the Pochhammer symbol, which is defined as
$(x)_{n}=\prod_{i=0}^{n-1}(x+i)$.

Two hypergeometric functions are called _contiguous_ if they have the same
variable and two equal parameters, while the third parameter differs by an
integer. It is known [2, Chapter 2.5] that for any three contiguous Gauss
hypergeometric functions, there is a linear relation with rational
coefficients depending on the parameters and the variable. We use the
following relation

$\alpha(1-z){}{}_{2}F_{1}(\alpha+1,\beta;\gamma;z)+(\gamma-2\alpha-(\beta-\alpha)z){}_{2}F_{1}(\alpha,\beta;\gamma;z)-(\gamma-\alpha){}_{2}F_{1}(\alpha-1,\beta;\gamma;z)=0\,.$
(13)

We upper bound the sum in (12) by a hypergeometric function and then use (13)
to determine its value. For this, observe that if one of the parameters
$\alpha$ or $\beta$ of a hypergeometric function is a negative integer, it
simplifies to a polynomial. For example, let $\beta=-m$ where
$m\in\mathbb{N}$. Then, we get

${}_{2}F_{1}(\alpha,-m,\gamma,z)=\sum_{n=0}^{m}(-1)^{n}\frac{m!}{(m-n)!}\frac{(\alpha)_{n}}{(\gamma)_{n}}\frac{z^{n}}{n!}=\sum_{n=0}^{m}(-1)^{n}\binom{m}{n}\frac{(\alpha)_{n}}{(\gamma)_{n}}z^{n}\,.$

Furthermore, we have

$\displaystyle\sum_{i=1}^{b}i(d-1)^{i-1}\prod_{j=1}^{i-1}\frac{b-j}{kb-(b-1)+j}$
$\displaystyle\leq\sum_{i=1}^{b}i(d-1)^{i-1}\prod_{j=1}^{i-1}\frac{b-j}{db-(b-1)+j}$
$\displaystyle=\sum_{i=0}^{b-1}(i+1)(d-1)^{i}\prod_{j=0}^{i-1}\frac{b-1-j}{(d-1)b+2+j}$
$\displaystyle=\sum_{i=0}^{b-1}\frac{(i+1)!}{i!}(-1)^{i}(1-d)^{i}\frac{(b-1)!}{(b-1-i)!}\frac{1}{\big{(}(d-1)b+2\big{)}_{i}}$
$\displaystyle=\sum_{i=0}^{b-1}(-1)^{i}\binom{b-1}{i}\frac{(2)_{i}}{\big{(}(d-1)b+2\big{)}_{i}}(1-d)^{i}$
$\displaystyle={}_{2}F_{1}(2,1-b;(d-1)b+2;1-d)\,.$

Using (13) with $\alpha=1$, $\beta=1-b$, $\gamma=(d-1)b+2$ and $z=1-d$ yields
the coefficients $\alpha(1-z)=d$, $\gamma-2\alpha-(\beta-\alpha)z=0$ and
$\gamma-\alpha=db-(b-1)$. Moreover, it holds that $F(0,\beta;\gamma;z)=1$.
Hence, we get

${}_{2}F_{1}(2,1-b;(d-1)b+2;1-d)=b-\frac{b-1}{d}\leq b\,,$

implying (11). All that is left to show now is

$\lim_{b\rightarrow\infty}\binom{kb}{b-1}\frac{1}{(d-1)^{b-1}}\left(1-\frac{1}{d}\right)^{kb}=0\,.$

Here, we will use the Stirling approximation for $\binom{kb}{b-1}$, which
yields

$\displaystyle\binom{kb}{b-1}\frac{1}{(d-1)^{b-1}}\left(1-\frac{1}{d}\right)^{kb}\sim\,$
$\displaystyle\sqrt{\frac{kb}{2\pi(b-1)(kb-b+1)}}$
$\displaystyle\cdot\frac{(kb)^{kb}}{(b-1)^{b-1}(kb-b+1)^{kb-b+1}}\cdot\frac{(d-1)^{kb-b+1}}{d^{kb}}\,.$

First, notice that the root converges to $0$ if $b\rightarrow\infty$, which
means that we only have to upper bound the remaining terms by a constant in
order to finish the proof. We have

$\displaystyle\frac{(kb)^{kb}}{(b-1)^{b-1}(kb-b+1)^{kb-b+1}}\cdot\frac{(d-1)^{kb-b+1}}{d^{kb}}$
$\displaystyle\leq\frac{1}{(b-1)^{b-1}}\cdot\frac{(kb)^{kb}}{d^{kb}}\cdot\frac{(d-1)^{kb-b+1}}{((k-1)b)^{kb-b+1}}$
$\displaystyle=\left(\frac{b}{b-1}\right)^{b-1}\left(\frac{k}{d}\right)^{kb}\left(\frac{d-1}{k-1}\right)^{kb-b+1}\,.$

Note that the first term is upper bounded by $e$. Moreover, with the help of
the following lemma, we can upper bound the remaining terms by 1.

######  Lemma 6.

For all $k\geq 2$ and $d\geq 2$, it holds that

$\frac{k^{k}}{(k-1)^{k-1}}\leq\frac{d^{k}}{(d-1)^{k-1}}\,.$

###### Proof.

Consider the function $f(x)={x^{k}}/{(x-1)^{k-1}}$ for $x>1$. We show that
$x=k$ is a global minimum. It holds

$f^{\prime}(x)=\frac{x^{k-1}(x-k)}{(x-1)^{k}}\,.$

For $x>1$, we only have $f^{\prime}(x)=0$ if $x=k$. Furthermore, it holds

$f^{\prime\prime}(x)=\frac{(k-1)kx^{k-2}}{(x-1)^{k+1}}\,.$

It is easy to see that $f^{\prime\prime}(x)>0$ for all $k\geq 2$ and $x>1$.
Moreover, since $\lim_{x\rightarrow 1+}f(x)=\infty$ and
$\lim_{x\rightarrow\infty}f(x)=\infty$, we indeed have a global minimum at
$x=k$. This finishes the proof. ∎

Lemma 6 implies

$\left(\frac{k}{d}\right)^{k}\leq\left(\frac{k-1}{d-1}\right)^{k-1}\,,$

and since $x^{b}$ is strictly increasing in $x$ for $x>0$ and $b>0$, we have

$\left(\frac{k}{d}\right)^{kb}\left(\frac{d-1}{k-1}\right)^{kb-b+1}\leq\left(\frac{k-1}{d-1}\right)^{(k-1)b}\left(\frac{d-1}{k-1}\right)^{(k-1)b}\cdot\frac{d-1}{k-1}=\frac{d-1}{k-1}\leq
1\,,$

as $k\geq d\geq 2$. ∎

######  Theorem 6.

If $k\geq d\geq 2$, the competitive ratio $c^{*}$ is strictly increasing in
$b$, for $b\geq 1$.

###### Proof.

We prove that $c^{*}$ is strictly increasing in $b$ by showing

$\displaystyle c^{\prime}_{b}:=$
$\displaystyle\frac{1}{b}\left(\sum_{i=1}^{b}i\binom{kb}{b-i}\frac{1}{(d-1)^{b-i}}\right)\left(1-\frac{1}{d}\right)^{kb}>$
$\displaystyle\frac{1}{b+1}\left(\sum_{i=1}^{b+1}i\binom{k(b+1)}{b+1-i}\frac{1}{(d-1)^{b+1-i}}\right)\left(1-\frac{1}{d}\right)^{k(b+1)}=:c^{\prime}_{b+1}\,,$

for all $b\geq 1$, if $k\geq d\geq 2$. We do this by showing that
$c^{\prime}_{b+1}/c^{\prime}_{b}<1$. As detailed in the proof of Theorem 5, it
holds that

$c^{\prime}_{b}=\frac{{}_{2}F_{1}(2,1-b;(k-1)b+2;1-d)}{b}\binom{kb}{b-1}\frac{1}{(d-1)^{b-1}}\left(1-\frac{1}{d}\right)^{kb}\,.$

It follows that

$\frac{c^{\prime}_{b+1}}{c^{\prime}_{b}}=\frac{b\cdot{}_{2}F_{1}(2,-b;(k-1)(b+1)+2;1-d)}{(b+1)\cdot{}_{2}F_{1}(2,1-b;(k-1)b+2;1-d)}\cdot\frac{\binom{k(b+1)}{b}}{\binom{kb}{b-1}}\cdot\frac{(d-1)^{k-1}}{d^{k}}\,.$

######  Lemma 7.

For all $b\geq 1$ and $k\geq d\geq 2$, it holds that

$\frac{b\cdot{}_{2}F_{1}(2,-b;(k-1)(b+1)+2;1-d)}{(b+1)\cdot{}_{2}F_{1}(2,1-b;(k-1)b+2;1-d)}<1\,.$

###### Proof.

In the following, we fix $k\geq 2$ and $b\geq 1$. Then, we show that

$\frac{{}_{2}F_{1}(2,-b;(k-1)(b+1)+2;1-d)}{{}_{2}F_{1}(2,1-b;(k-1)b+2;1-d)}$

is maximized if $d$ is maximized, i.e. $d=k$. As shown in the proof of Theorem
5, we will then have for $d=k$

$\frac{\frac{1}{b+1}{}_{2}F_{1}(2,-b;(k-1)(b+1)+2;1-k)}{\frac{1}{b}{}_{2}F_{1}(2,1-b;(k-1)b+2;1-k)}=\frac{\frac{1}{b+1}\left(b+1-\frac{b}{k}\right)}{\frac{1}{b}\left(b-\frac{b-1}{k}\right)}=\frac{1-\frac{1}{k}\frac{b}{b+1}}{1-\frac{1}{k}\frac{b-1}{b}}<1\,,$

since $b/(b+1)>(b-1)/b$ for all $b\geq 1$. Recall, that

$\displaystyle{}_{2}F_{1}(2,-b;(k-1)(b+1)+2;1-d)$
$\displaystyle=\sum_{i=0}^{b}(i+1)(d-1)^{i}\frac{b!}{(b-i)!}\frac{1}{\left((k-1)(b+1)+2\right)_{i}}$
$\displaystyle=:\sum_{i=0}^{b}u_{i}\cdot(d-1)^{i}\,,$

and

$\displaystyle{}_{2}F_{1}(2,1-b;(k-1)b+2;1-d)$
$\displaystyle=\sum_{i=0}^{b-1}(i+1)(d-1)^{i}\frac{(b-1)!}{(b-1-i)!}\frac{1}{\left((k-1)b+2\right)_{i}}$
$\displaystyle=:\sum_{i=0}^{b-1}v_{i}\cdot(d-1)^{i}\,,$

where $u_{i}$ and $v_{i}$ are constants, since we fixed $k$ and $b$. This
means, that the fraction of the two hypergeometric functions is a quotient of
two real polynomials. Thus, we can use the following theorem given in [14].

######  Theorem 7 ([14, Theorem 4.4]).

Let $f_{n}(x)=\sum_{k=0}^{n}a_{k}x^{k}$ and
$g_{n}(x)=\sum_{k=0}^{n}b_{k}x^{k}$ be real polynomials, with $b_{k}>0$ for
all $k$. If the sequence $\\{a_{k}/b_{k}\\}$ is increasing (decreasing), then
so is the function $f_{n}(x)/g_{n}(x)$ for all $x>0$.

First, it is easy to see that $u_{i}>0$, for all $0\leq i\leq b$, and
$v_{i}>0$, for all $0\leq i\leq b-1$, hold. Thus, we can apply the theorem
above to the fraction

$\frac{f(d)}{g(d)}:=\frac{\sum_{i=0}^{b-1}u_{i}(d-1)^{i}}{\sum_{i=0}^{b-1}v_{i}(d-1)^{i}}\,.$

We will show that $(u_{i}/v_{i})_{0\leq i\leq b-1}$ forms an increasing
sequence, implying that $f/g$ is increasing for all $d>1$. Moreover, we have
that

$\frac{u_{b}(d-1)^{b}}{\sum_{i=0}^{b-1}v_{i}(d-1)^{i}}$

is increasing for $d>1$, because the reciprocal

$\sum_{i=0}^{b-1}\frac{v_{i}}{u_{b}}\cdot\frac{1}{(d-1)^{b-i}}$

is decreasing as all the coefficients are greater than zero. It then
immediately follows that the considered fraction of hypergeometric functions
is increasing for $d>1$.

Hence, all that is left to prove is that $\left(u_{i}/v_{i}\right)_{0\leq
i\leq b-1}$ is indeed an increasing sequence, i.e.
$u_{i}/v_{i}>u_{i-1}/v_{i-1}$, for all $1\leq i\leq b-1$. We have

$\displaystyle\frac{u_{i}}{v_{i}}=\frac{b}{b-i}\frac{((k-1)b+2)_{i}}{((k-1)(b+1)+2)_{i}}\quad\text{and}\quad\frac{u_{i-1}}{v_{i-1}}=\frac{b}{b-i+1}\frac{((k-1)b+2)_{i-1}}{((k-1)(b+1)+2)_{i-1}}\,.$

Observe that

$\frac{u_{i}}{v_{i}}=\frac{u_{i-1}}{v_{i-1}}\cdot\frac{b-i+1}{b-i}\frac{(k-1)b+2+i-1}{(k-1)(b+1)+2+i-1}\,,$

meaning that we only have to show

$\frac{(k-1)b+2+i-1}{(k-1)(b+1)+2+i-1}>\frac{b-i}{b-i+1}\,.$

The left fraction is increasing in $i$, and thus lower bounded by

$\frac{(k-1)b+1}{(k-1)(b+1)+1}>\frac{b}{b+1}\,.$

On the other hand, $(b-i)/(b-i+1)$ is decreasing in $i$, and thus upper
bounded by $b/(b+1)$. This finishes the proof. ∎

######  Lemma 8.

For all $k\geq 2$ and all $b\geq 1$, it holds that

$\frac{\binom{k(b+1)}{b}}{\binom{kb}{b-1}}\leq\frac{k^{k}}{(k-1)^{k-1}}\,.$

###### Proof.

We prove this by considering the fraction $\binom{k(b+1)}{b+1}/\binom{kb}{b}$,
which is closely related to the desired fraction of binomial coefficients in
the sense that

$\frac{\binom{k(b+1)}{b}}{\binom{kb}{b-1}}=\frac{b+1}{b}\frac{(k-1)b+1}{(k-1)(b+1)+1}\frac{\binom{k(b+1)}{b+1}}{\binom{kb}{b}}\,.$
(14)

We upper bound said fraction of binomial coefficients by applying upper and
lower bounds for $n!$. The Stirling approximation yields

$\sqrt{2\pi}n^{n+\frac{1}{2}}e^{-n}e^{\frac{1}{12n+1}}<n!<\sqrt{2\pi}n^{n+\frac{1}{2}}e^{-n}e^{\frac{1}{12n}}\,.$

We can rewrite the fraction of binomial coefficients as

$\frac{\binom{k(b+1)}{b+1}}{\binom{kb}{b}}=\frac{1}{b+1}\frac{\big{(}k(b+1)\big{)}!}{\big{(}(k-1)(b+1)\big{)}!}\frac{\big{(}(k-1)b\big{)}!}{(kb)!}\,.$

Now, we apply the upper bound in the numerator and the lower bound in the
denominator

$\displaystyle\frac{\binom{k(b+1)}{b+1}}{\binom{kb}{b}}<\frac{1}{b+1}$
$\displaystyle\frac{\big{(}k(b+1)\big{)}^{k(b+1)+\frac{1}{2}}e^{-k(b+1)}}{\big{(}(k-1)(b+1)\big{)}^{(k-1)(b+1)+\frac{1}{2}}e^{-(k-1)(b+1)}}\cdot
e^{\frac{1}{12k(b+1)}-\frac{1}{12(k-1)(b+1)+1}}$
$\displaystyle\frac{\big{(}(k-1)b\big{)}^{(k-1)b+\frac{1}{2}}e^{-(k-1)b}}{\big{(}kb\big{)}^{kb+\frac{1}{2}}e^{-kb}}\cdot
e^{\frac{1}{12(k-1)b}-\frac{1}{12kb+1}}\,.$

It holds that

$\frac{1}{12k(b+1)}-\frac{1}{12(k-1)(b+1)+1}<0\quad\text{and}\quad\frac{1}{12(k-1)b}-\frac{1}{12kb+1}<\frac{1}{12(k-1)b}\,,$

which implies

$\displaystyle\frac{\binom{k(b+1)}{b+1}}{\binom{kb}{b}}$
$\displaystyle<\frac{1}{b+1}\left(\frac{k}{k-1}\right)^{(k-1)(b+1)+\frac{1}{2}}k^{b+1}(b+1)^{b+1}e^{-(b+1)}$
$\displaystyle\phantom{<}\,\cdot\left(\frac{k-1}{k}\right)^{(k-1)b+\frac{1}{2}}\left(\frac{1}{k}\right)^{b}\left(\frac{1}{b}\right)^{b}e^{b}e^{\frac{1}{12(k-1)b}}$
$\displaystyle=\frac{k^{k}}{(k-1)^{k-1}}\left(\frac{b+1}{b}\right)^{b}\frac{1}{e}e^{\frac{1}{12(k-1)b}}\,.$

Plugging this into equation (14) then yields

$\frac{\binom{k(b+1)}{b}}{\binom{kb}{b-1}}<\frac{(k-1)b+1}{(k-1)(b+1)+1}\frac{k^{k}}{(k-1)^{k-1}}\left(\frac{b+1}{b}\right)^{b+1}\frac{1}{e}e^{\frac{1}{12(k-1)b}}\,.$

Thus, in order to prove the desired upper bound, we have to show

$\left(\frac{b+1}{b}\right)^{b+1}\frac{(k-1)b+1}{(k-1)(b+1)+1}e^{\frac{1}{12(k-1)b}}\leq
e\,.$

Notice that all terms are decreasing in $k$, for $k\geq 2$, meaning that we
can upper bound the left-hand side by

$\left(\frac{b+1}{b}\right)^{b+1}\frac{(k-1)b+1}{(k-1)(b+1)+1}e^{\frac{1}{12(k-1)b}}\leq\left(\frac{b+1}{b}\right)^{b+1}\frac{b+1}{b+2}e^{\frac{1}{12b}}=\left(\frac{b+1}{b}\right)^{b}\frac{(b+1)^{2}}{b(b+2)}e^{\frac{1}{12b}}\,.$

As a next step, we take logarithms on both sides. We make use the following
useful inequality, which is true for $x>0$

$\ln\left(1+x\right)\leq\frac{x(6+x)}{6+4x}\,.$

We obtain

$\displaystyle
b\ln\left(1+\frac{1}{b}\right)+\ln\left(1+\frac{1}{b^{2}+2b}\right)+\frac{1}{12b}\leq\frac{6b+1}{6b+4}+\frac{1}{b^{2}+2b}+\frac{1}{12b}\overset{!}{\leq}1\,,$

where we also used the simpler upper bound $\ln(1+x)\leq x$ for the second
term. One can show that the inequality above is indeed satisfied for $b>1.66$.
This means that we have to show the case $b=1$ separately. There, we have

$\frac{\binom{2k}{1}}{\binom{k}{0}}=2k\leq\left(\frac{k}{k-1}\right)^{k-1}k=\frac{k^{k}}{(k-1)^{k-1}}\,,$

where the first inequality is true as $k\geq 2$. ∎

Finally, we can finish the proof of Theorem 6 with the help of Lemmas 7 and 8.
We have

$\displaystyle\frac{c^{\prime}_{b+1}}{c^{\prime}_{b}}$
$\displaystyle=\frac{b\cdot{}_{2}F_{1}(2,-b;(k-1)(b+1)+2;1-d)}{(b+1)\cdot{}_{2}F_{1}(2,1-b;(k-1)b+2;1-d)}\cdot\frac{\binom{k(b+1)}{b}}{\binom{kb}{b-1}}\cdot\frac{(d-1)^{k-1}}{d^{k}}$
$\displaystyle<1\cdot\frac{k^{k}}{(k-1)^{k-1}}\cdot\frac{(d-1)^{k-1}}{d^{k}}\leq
1\,,$

where the last step is true according to Lemma 6. ∎

## References

  * [1] G. Aggarwal, G. Goel, C. Karande, and A. Mehta.  Online vertex-weighted bipartite matching and single-bid budgeted allocations.  In Proc. 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1253–1264. SIAM, 2011.
  * [2] George E. Andrews, Richard Askey, and Ranjan Roy.  Special Functions.  Encyclopedia of Mathematics and its Applications. Cambridge University Press, 1999.
  * [3] Y. Azar, I.R. Cohen, and A. Roytman.  Online lower bounds via duality.  In Proc. 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1038–1050. SIAM, 2017.
  * [4] N. Buchbinder, K. Jain, and J. Naor.  Online primal-dual algorithms for maximizing ad-auctions revenue.  In Proc. 15th Annual European Symposium on Algorithms (ESA), Springer LNCS, Volume 4698, pages 253–264, 2007.
  * [5] K. Chaudhuri, C. Daskalakis, R.D. Kleinberg, and H. Lin.  Online bipartite perfect matching with augmentations.  In Proc. 28th IEEE International Conference on Computer Communications (INFOCOM), pages 1044–1052, 2009.
  * [6] I.R. Cohen and D. Wajc.  Randomized online matching in regular graphs.  In Proc. 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 960–979. SIAM, 2018.
  * [7] R. Cole, K. Ost, and S. Schirra.  Edge-coloring bipartite multigraphs in $O(E\log D)$ time.  Comb., 21(1):5–12, 2001.
  * [8] J. Csima and L. Lovász.  A matching algorithm for regular bipartite graphs.  Discret. Appl. Math., 35(3):197–203, 1992.
  * [9] N.R. Devanur and T.P. Hayes.  The adwords problem: online keyword matching with budgeted bidders under random permutations.  In Proc. 10th ACM Conference on Electronic Commerce (EC), pages 71–78. ACM, 2009.
  * [10] N.R. Devanur, B. Sivan, and Y. Azar.  Asymptotically optimal algorithm for stochastic adwords.  In Proc. 13th ACM Conference on Electronic Commerce (EC), pages 388–404. ACM, 2012.
  * [11] A. Goel, M. Kapralov, and S. Khanna.  Perfect matchings in $O(n\log n)$ time in regular bipartite graphs.  SIAM J. Comput., 42(3):1392–1404, 2013.
  * [12] R.L. Graham, D.E. Knuth, and O. Patashnik.  Concrete Mathematics: A Foundation for Computer Science.  Addison-Wesley, 1989.
  * [13] E.F. Grove, M.-Y. Kao, P. Krishnan, and J.S. Vitter.  Online perfect matching and mobile computing.  In Proc. 4th International Workshop on Algorithms and Data Structures (WADS), LNCS, Volume 955, pages 194–205. Springer, 1995.
  * [14] V. Heikkala, M.K. Vamanamurthy, and M. Vuorinen.  Generalized elliptic integrals.  Comput. Methods Funct. Theory, 9(1):75–109, 2009.
  * [15] P. Jaillet and X. Lu.  Online stochastic matching: New algorithms with better bounds.  Math. Oper. Res., 39(3):624–646, 2014.
  * [16] B. Kalyanasundaram and K. Pruhs.  An optimal deterministic algorithm for online b-matching.  Theor. Comput. Sci., 233(1-2):319–325, 2000.
  * [17] R.M. Karp, U.V. Vazirani, and V.V. Vazirani.  An optimal algorithm for on-line bipartite matching.  In Proc. 22nd Annual ACM Symposium on Theory of Computing (STOC), pages 352–358, 1990.
  * [18] M. Mahdian and Q. Yan.  Online bipartite matching with random arrivals: An approach based on strongly factor-revealing LPs.  In Proc. 43rd ACM Symposium on Theory of Computing (STOC), pages 597–606, 2011.
  * [19] V.H. Manshadi, S. Oveis Gharan, and A. Saberi.  Online stochastic matching: Online actions based on offline statistics.  Math. Oper. Res., 37(4):559–573, 2012.
  * [20] A. Mehta, A. Saberi, U.V. Vazirani, and V.V. Vazirani.  Adwords and generalized online matching.  J. ACM, 54(5):22, 2007.
  * [21] J. Naor and D. Wajc.  Near-optimum online ad allocation for targeted advertising.  ACM Trans. Economics and Comput., 6(3-4):16:1–16:20, 2018.
  * [22] A. Schrijver.  Bipartite edge coloring in $O(\Delta m)$ time.  SIAM J. Comput., 28(3):841–846, 1998.
  * [23] V.V. Vazirani.  Randomized online algorithms for Adwords.  CoRR, abs/2107.10777, 2021.


$\mathfrak{D}\models Q$ iff $\mathfrak{D}\models\eta_{C}(Q)$.

######  Lemma 23.

If $\mathfrak{D}\models Q$ then there is an $\mathbf{S}$-database
$\mathfrak{D}^{\ast}$ of tree-width at most $\max\\{0,0pt{\mathcal{O}}-1\\}$
such that

  1. 1.

$\mathfrak{D}^{\ast}\models Q$,

  2. 2.

there is a homomorphism from $\mathfrak{D}^{\ast}$ to $\mathfrak{D}$.

Moreover, if $q$ is a Boolean CQ of tree-width at most $w\geq 0$ and
$\mathfrak{D}\models q$, then there is an $\mathbf{S}$-database
$\mathfrak{D}^{\ast}$ of tree-width at most $w$ such that

  1. 1.

$\mathfrak{D}^{\ast}\models q$,

  2. 2.

there is a homomorphism from $\mathfrak{D}^{\ast}$ to $\mathfrak{D}$.

######  Lemma 24.

If $Q\in{(\mathsf{G},\mathsf{AQ}_{0})}$ is an OMQ with data schema
$\mathbf{S}$ and $\mathfrak{D}\models Q$, then there is an acyclic
$\mathfrak{D}^{\ast}$ such that

  1. 1.

$\mathfrak{D}^{\ast}\models Q$ and

  2. 2.

there is a homomorphism from $\mathfrak{D}^{\ast}$ to $\mathfrak{D}$.

Moreover, an according statement holds for acyclic Boolean CQs as well.

The following lemma will be the main ingredient towards a proof of Theorem 13:

######  Lemma 25.

$Q$ is FO-rewritable iff $\eta_{C}(Q)$ is.

######  Proof 7.

Throughout the proof, let $w=\max\\{0,0pt{\mathcal{O}}-1\\}$.

Suppose first that $Q$ is FO-rewritable and let $q=\bigvee_{i=1}^{n}p_{i}$ be
a UCQ equivalent to $Q$.

######  Claim.

The UCQ $q$ is equivalent to a UCQ whose disjuncts are all of tree-width at
most $w$.

######  Proof 8.

Let $q^{\prime}$ be a UCQ that contains a disjunct $p^{\prime}$ iff  (i)
$p^{\prime}$has tree-width at most $w$,  (ii) $p^{\prime}\subseteq p_{i}$for
some $i=1,\ldots,n$, and  (iii) $p^{\prime}$is minimal with respect to these
properties.  Moreover, we require from that no disjunct in $q^{\prime}$ is
homomorphically equivalent to another disjunct of $q^{\prime}$. Thus,
$q^{\prime}$ is indeed a finite UCQ. We show that $q$ is equivalent to
$q^{\prime}$.

Suppose first that $\mathfrak{D}\models q$. Then also $\mathfrak{D}\models Q$
and, by Lemma 23, there is an $\mathbf{S}$-database $\mathfrak{D}^{\ast}$ of
tree-width at most $w$ such that $\mathfrak{D}^{\ast}\models Q$ and
$\mathfrak{D}^{\ast}$ maps to $\mathfrak{D}$. Thus, also
$\mathfrak{D}^{\ast}\models q$. Since $\mathfrak{D}^{\ast}$ has tree-width at
most $w$, there is a disjunct $p$ in $q^{\prime}$ and a
$\mathfrak{D}^{\prime}\subseteq\mathfrak{D}^{\ast}$ such that $p$ is
homomorphically equivalent to $\mathfrak{D}^{\prime}$. Thus
$\mathfrak{D}^{\prime}\models p$ and so $\mathfrak{D}^{\ast}\models p$. Since
$\mathfrak{D}^{\ast}$ maps homomorphically to $\mathfrak{D}$, we have
$\mathfrak{D}\models p$ and so $\mathfrak{D}\models q^{\prime}$ follows.

Suppose now that $\mathfrak{D}\models q^{\prime}$, i.e., $\mathfrak{D}\models
p$ for some disjunct $p$ of $q^{\prime}$. Since $p\subseteq p_{i}$ for some
$i=1,\ldots,n$, there is a homomorphism from $p_{i}$ to $p$. Hence, it follows
that $\mathfrak{D}\models p_{i}$ and thus $\mathfrak{D}\models q$.

Suppose now that each $p_{i}$ ($i=1,\ldots,n$) has tree-width at most $w$. Let
$\delta_{i}={(\mathcal{T}_{i},{(X_{i,v})}_{v\in T_{i}})}$ be a tree
decomposition of $p_{i}$ of width at most $w$. A _variant_ of $p_{i}$ is a CQ
$p$ over $(\mathbf{S}\cup\\{C\\})$ that  (i) results from $p_{i}$ by adding a
set of atoms of the form $C(x_{0},\ldots,x_{w})$ with
$\\{x_{0},\ldots,x_{w}\\}\subseteq X_{i,v}$ for some $v\in T_{i}$, and  (ii)
is acyclic.  We let $p_{i}^{\prime}$ be the UCQ over $(\mathbf{S}\cup\\{C\\})$
that contains a disjunct for each variant of $p_{i}$. Moreover, we let
$q^{\prime}=\bigvee_{i=1}^{n}p_{i}^{\prime}$ and assume again that
$q^{\prime}$ contains no two distinct disjuncts that are homomorphically
equivalent. Obviously, $q^{\prime}$ is a finite UCQ, and we claim that
$q^{\prime}$ is a UCQ-rewriting of $\eta_{C}(Q)$.

Indeed, suppose $\mathfrak{D}$ is an $(\mathbf{S}\cup\\{C\\})$-database such
that $\mathfrak{D}\models\eta_{C}(Q)$. According to Lemma 24, there is an
acyclic $(\mathbf{S}\cup\\{C\\})$-database $\mathfrak{D}^{\ast}$ such that
$\mathfrak{D}^{\ast}\models\eta_{C}(Q)$ and such that $\mathfrak{D}^{\ast}$
maps homomorphically to $\mathfrak{D}$. By Lemma 22 we have
$\mathfrak{D}^{\ast}\models Q$ as well. Let $\mathfrak{D}^{\ast}[\mathbf{S}]$
denote the database $\mathfrak{D}^{\ast}$ restricted to $\mathbf{S}$. Since
$C$ does not appear in $Q$, we must have
$\mathfrak{D}^{\ast}[\mathbf{S}]\models Q$ as well and so
$\mathfrak{D}^{\ast}[\mathbf{S}]\models p_{i}$ for some $i=1,\ldots,n$. It is
now easy to check that there is a variant $p$ of $p_{i}$ such that
$\mathfrak{D}^{\ast}\models p$. Hence, $\mathfrak{D}^{\ast}\models q^{\prime}$
and so $\mathfrak{D}\models q^{\prime}$ as required.

Conversely, suppose that $\mathfrak{D}\models q^{\prime}$, i.e.,
$\mathfrak{D}\models p$ for some CQ $p$ that is a variant of some $p_{i}$. By
Lemma 24 there is an acyclic $(\mathbf{S}\cup\\{C\\})$-database
$\mathfrak{D}^{\ast}$ such that $\mathfrak{D}^{\ast}\models p$ and
$\mathfrak{D}^{\ast}$ homomorphically maps to $\mathfrak{D}$. Obviously, there
is a homomorphism from $p_{i}$ to $p$, since $p$ is a variant and results from
$p_{i}$ just by adding atoms. Hence, also $\mathfrak{D}^{\ast}\models p_{i}$
and thus $\mathfrak{D}^{\ast}\models q$ follows. We then obtain
$\mathfrak{D}^{\ast}\models Q$ and by Lemma 22 also
$\mathfrak{D}^{\ast}\models\eta_{C}(Q)$. Since $\eta_{C}(Q)$ is closed under
homomorphisms, $\mathfrak{D}\models\eta_{C}(Q)$ follows.

Suppose now that $\eta_{C}(Q)$ is FO-rewritable and let
$q=\bigvee_{i=1}^{n}p_{i}$ be a UCQ equivalent to $\eta_{C}(Q)$. We show that
$Q$ is FO-rewritable as well. In this case, we can assume that $q$ is actually
a disjunction of acyclic CQs, a proof of this fact can be obtained similarly
to the claim above and is left to the reader. Let $p_{i}^{\prime}$ be the CQ
that results from $p_{i}$ by dropping all atoms of the form
$C(x_{0},\ldots,x_{w})$. Moreover, let
$q^{\prime}=\bigvee_{i=1}^{n}p_{i}^{\prime}$. We claim that $q^{\prime}$ is a
UCQ equivalent to $Q$.

Suppose first that $\mathfrak{D}\models Q$. By Lemma 23 there is an
$\mathbf{S}$-database $\mathfrak{D}^{\ast}$ of tree-width at most $w$ such
that $\mathfrak{D}^{\ast}\models Q$ and $\mathfrak{D}^{\ast}$ homomorphically
maps to $\mathfrak{D}$. Fix a tree decomposition
$\delta^{\ast}={(\mathcal{T},{(X_{v})}_{v\in T})}$ of $\mathfrak{D}^{\ast}$.
We can turn $\mathfrak{D}^{\ast}$ into an acyclic
$(\mathbf{S}\cup\\{C\\})$-database by adding to $\mathfrak{D}^{\ast}$ all
facts of the form $C(a_{0},\ldots,a_{w})$ such that
$\\{a_{0},\ldots,a_{w}\\}\subseteq X_{v}$ for some $v\in T$. Call the
resulting database $\mathfrak{D}^{\prime}$. Obviously,
$\mathfrak{D}^{\prime}\models Q$ and since $\mathfrak{D}^{\prime}$ is acyclic,
we obtain $\mathfrak{D}^{\prime}\models\eta_{C}(Q)$ by Lemma 22. Therefore,
$\mathfrak{D}^{\prime}\models p_{i}$ for some $i=1,\ldots,n$. Since
$p_{i}^{\prime}$ contains no atoms of the form $C(x_{0},\ldots,x_{w})$, it
follows that $\mathfrak{D}^{\prime}\models p_{i}^{\prime}$ as well and so
$\mathfrak{D}^{\ast}\models p_{i}^{\prime}$. Thus $\mathfrak{D}\models
p_{i}^{\prime}$ and so $\mathfrak{D}\models q^{\prime}$ as required.

Conversely, suppose now that $\mathfrak{D}\models q^{\prime}$, i.e.,
$\mathfrak{D}\models p_{i}^{\prime}$ for some $i=1,\ldots,n$. Notice that
$p_{i}^{\prime}$ has tree-width at most $w$ by construction. Using Lemma 23,
we infer that there is an $\mathbf{S}$-database $\mathfrak{D}^{\ast}$ such
that $\mathfrak{D}^{\ast}\models p_{i}^{\prime}$ and such that there is a
homomorphism $h$ from $\mathfrak{D}^{\ast}$ to $\mathfrak{D}$. Now fix a tree
decomposition $\delta_{i}={(\mathcal{T},{(X_{v})}_{v\in T})}$ of
$p_{i}^{\prime}$ of width at most $w$. We can see $\delta_{i}$ also as a tree
decomposition of $p_{i}$ that witnesses that $p_{i}$ is acyclic. Now we extend
$\mathfrak{D}^{\ast}$ to an $(\mathbf{S}\cup\\{C\\})$-database as follows.
Suppose $C(x_{0},\ldots,x_{w})$ occurs in $p_{i}$ but has been deleted from
$p_{i}^{\prime}$. Then $\\{x_{0},\ldots,x_{w}\\}\subseteq X_{v}$ for some
$v\in T$. We can assume w.l.o.g that
$\mathsf{dom}(h)\cap\\{x_{0},\ldots,x_{w}\\}\neq\emptyset$; otherwise we can
drop that atom from $p_{i}$. Pick a
$y\in\mathsf{dom}(h)\cap\\{x_{0},\ldots,x_{w}\\}$. Now we add to
$\mathfrak{D}^{\ast}$ the atom $C(a_{0},\ldots,a_{w})$, where $a_{i}=h(x_{i})$
if $x_{i}\in\mathsf{dom}(h)$ and $a_{i}=h(y)$ otherwise. We repeat this
construction for all occurrences of an atom of the form
$C(x_{0},\ldots,x_{w})$ in $p_{i}$. Call the resulting database
$\mathfrak{D}^{\prime}$. It is clear that $h$ is a homomorphism from $p_{i}$
to $\mathfrak{D}^{\prime}$. Notice also that
$\mathfrak{D}^{\prime}[\mathbf{S}]=\mathfrak{D}^{\ast}$. Now since
$\mathfrak{D}^{\prime}\models p_{i}$, we must have
$\mathfrak{D}^{\prime}\models\eta_{C}(Q)$ and so by Lemma 24 there is an
acyclic $(\mathbf{S}\cup\\{C\\})$-database $\mathfrak{D}^{\prime\prime}$ such
that $\mathfrak{D}^{\prime\prime}\models\eta_{C}(Q)$ and
$\mathfrak{D}^{\prime\prime}$ homomorphically maps to $\mathfrak{D}^{\prime}$.
By Lemma 22 we have $\mathfrak{D}^{\prime\prime}\models Q$ as well and hence
also $\mathfrak{D}^{\prime}\models Q$. But
$\mathfrak{D}^{\prime}[\mathbf{S}]=\mathfrak{D}^{\ast}$, whence
$\mathfrak{D}^{\ast}\models Q$ follows since $C$ does not occur in $Q$. Since
$\mathfrak{D}^{\ast}$ homomorphically maps to $\mathfrak{D}$, we obtain
$\mathfrak{D}\models Q$ as required.

###  D.2 Proof of Theorem 13

Lower bounds. Since, according to Bienvenu et al. (2016), FO-rewritability for
the class ${(\mathcal{ELI},\mathsf{BCQ})}$ is already hard for 2ExpTime
according to Bienvenu et al. (2016), the following hardness results follow
immediatlely:

  * •

2ExpTime-hardness for $\mathsf{FORew(\mathsf{C},\mathsf{Q})}$ with
$\mathsf{C}\in\\{\mathsf{G},\mathsf{FG}\\}$ and
$\mathsf{Q}\in\\{\mathsf{CQ},\mathsf{UCQ}\\}$;

  * •

2ExpTime-hardness for $\mathsf{FORew(\mathsf{FG},\mathsf{AQ}_{0})}$.

Moreover, in Bienvenu et al. (2013), it is shown that
$\mathsf{FORew(\mathcal{ELI},AQ_{0})}$ is ExpTime-hard. Therefore, for OMQs of
bounded arity, ExpTime-hardness for
$\mathsf{FORew(\mathsf{G},\mathsf{AQ}_{0})}$ follows.

The only missing lower bound is therefore the 2ExpTime lower bound for
$\mathsf{FORew(\mathsf{G},\mathsf{AQ}_{0})}$.

Let $Q_{1}$ and $Q_{2}$ be Boolean OMQs with data schema $\mathbf{S}$. We say
that $Q_{1}$ is _contained_ in $Q_{2}$, if $\mathfrak{D}\models Q_{1}$ implies
$\mathfrak{D}\models Q_{2}$ for every $\mathbf{S}$-database $\mathfrak{D}$. We
are going to use the following result which is implicit in Barceló et al.
(2014):

######  Theorem 26.

The problem of deciding whether a OMQ $Q_{1}={(\mathbf{S},\mathcal{O},G_{1})}$
from ${(\mathsf{G},\mathsf{AQ}_{0})}$ is contained in an OMQ
$Q_{2}={(\mathbf{S},\mathcal{O},G_{2})}$ is hard for 2ExpTime. This is true
even for the case where $Q_{2}$ is FO-rewritable.

######  Remark.

In Barceló et al. (2014), a slightly different statement is proved. The
authors prove in fact that deciding whether a _guarded Datalog_ program is
contained in a Boolean acyclic UCQ is hard for 2ExpTime. Guarded Datalog can
easily be seen as a fragment of ${(\mathsf{G},\mathsf{AQ}_{0})}$. Moreover, a
Boolean acyclic UCQ can easily be written as an OMQ from
${(\mathsf{G},\mathsf{AQ}_{0})}$ (cf. the discussion of “unfolding” strictly
acyclic queries in the definition of treeifications).

To prove that $\mathsf{FORew(\mathsf{G},\mathsf{AQ}_{0})}$ is hard for
2ExpTime, we are going to reduce the problem mentioned in Theorem 26 to
$\mathsf{FORew(\mathsf{G},\mathsf{AQ}_{0})}$.

Let $Q_{1}={(\mathbf{S},\mathcal{O}_{1},G_{1})}$ and
$Q_{2}={(\mathbf{S},\mathcal{O}_{2},G_{2})}$ be as in the hypothesis of
Theorem 26. Without loss of generality, we may assume that the predicates
$Q_{1}$ and $Q_{2}$ use and that do not appear in $\mathbf{S}$ are distinct.
We are going to construct an OMQ $Q^{\prime}$ that falls in
${(\mathsf{G},\mathsf{AQ}_{0})}$ such that $Q^{\prime}$ is FO-rewritable iff
$Q_{1}$ is contained in $Q_{2}$.

Let $Q^{\prime}={(\mathbf{S},\mathcal{O}^{\prime},G_{2})}$, where

  * •

$\mathbf{S}^{\prime}=\mathbf{S}\cup\\{R/2,A/1,B/1\\}$;

  * •

$\mathcal{O}^{\prime}$ is the union of $\mathcal{O}_{1}$ and $\mathcal{O}_{2}$
plus the rules

$\displaystyle R(x,y),A(y)$ $\displaystyle\rightarrow A(x),$ $\displaystyle
A(x),B(x),G_{1}$ $\displaystyle\rightarrow G_{2}.$

Notice that $G_{2}$ is also the query component of $Q^{\prime}$.

######  Lemma 27.

$Q_{1}$ is contained in $Q_{2}$ iff $Q^{\prime}$ is FO-rewritable.

######  Proof 9.

Assume first that $Q_{1}$ is not contained in $Q_{2}$. Then there is an
$\mathbf{S}$-database $\mathfrak{D}$ such that $\mathfrak{D}\models Q_{1}$ and
$\mathfrak{D}\not\models Q_{2}$. By Lemma 14, there is a $\mathfrak{D}^{\ast}$
of tree-width at most $\max\\{0,0pt{\mathbf{S}}-1\\}$ such that
$\mathfrak{D}^{\ast}\models Q_{1}$. Moreover, there also is a homomorphism
from $\mathfrak{D}^{\ast}$ to $\mathfrak{D}$. Since $Q_{2}$ is closed under
homomorphisms, we must also have $\mathfrak{D}^{\ast}\not\models Q_{2}$. For
each $k>0$, let $\mathfrak{D}_{k}$ be the $\mathbf{S}^{\prime}$-database
extending $\mathfrak{D}^{\ast}$ with the facts

$\displaystyle B(a_{0}),R(a_{0},a_{1}),\ldots,R(a_{k-1},a_{k}),A(a_{k}),$

where $a_{0},\ldots,a_{k}$ do not occur in
$\mathsf{adom}(\mathfrak{D}^{\ast})$. It is easy to check that
$\mathfrak{D}_{k}\models Q^{\prime}$ for all $k>0$. Moreover, no proper subset
of $\mathfrak{D}_{k}$ satisfies $Q^{\prime}$. By virtue of Theorem 1,
$Q^{\prime}$ is thus not FO-rewritable.

Conversely, suppose that $Q_{1}$ is contained in $Q_{2}$. Recall that $Q_{2}$
is FO-rewritable and, therefore, there is a UCQ $q$ over $\mathbf{S}$ that is
equivalent to $Q_{2}$. We claim that $q$ is a UCQ-rewriting for $Q^{\prime}$
as well.

Indeed, suppose first that $\mathfrak{D}\models q$ for some
$\mathbf{S}^{\prime}$-database $\mathbf{S}$. Since $q$ uses only symbols from
$\mathbf{S}$, we obtain that $\mathfrak{D}[\mathbf{S}]\models q$ as well.
Since $q$ is equivalent to $Q_{2}$, we get $\mathfrak{D}[\mathbf{S}]\models
Q_{2}$ and, by construction of $Q^{\prime}$, so $\mathfrak{D}\models
Q^{\prime}$.

Suppose now that $\mathfrak{D}\models Q^{\prime}$ for some
$\mathbf{S}^{\prime}$-database $\mathfrak{D}$. By construction of
$Q^{\prime}$, we must then have $\mathfrak{D}\models Q_{2}$ or
$\mathfrak{D}\models Q_{1}$. In the former case, we are done since $Q_{2}$ and
$q$ are equivalent. In the latter case, we get
$\mathfrak{D}[\mathbf{S}]\models Q_{1}$ whence
$\mathfrak{D}[\mathbf{S}]\models Q_{2}$ since $Q_{1}$ is contained in $Q_{2}$.
Therefore also $\mathfrak{D}[\mathbf{S}]\models q$ and thus
$\mathfrak{D}\models q$. This proves the claim.

It is clear that $Q^{\prime}$ can be constructed from $Q_{1}$ and $Q_{2}$ in
polynomial time. Therefore, 2ExpTime-hardness for
$\mathsf{FORew(\mathsf{G},\mathsf{AQ}_{0})}$ follows by Lemma 27.

Upper bounds. We shall now prove that
$\mathsf{FORew(\mathsf{FG},\mathsf{UCQ})}$ is in 2ExpTime. Following a similar
result for description logics in Bienvenu et al. (2016), we first show that we
can focus on Boolean UCQs:

######  Lemma 28.

Let $\mathsf{C}\in\\{\mathsf{FG},\mathsf{G}\\}$. Then
$\mathsf{FORew(\mathsf{C},\mathsf{UCQ})}$ can be reduced in polynomial time to
$\mathsf{FORew(\mathsf{C},\mathsf{UBCQ})}$.

######  Proof 10 (sketch).

Let $Q={(\mathbf{S},\mathcal{O},q(\bar{x}))}$ be an OMQ from
${(\mathsf{C},\mathsf{UCQ})}$ with $\bar{x}=x_{1},\ldots,x_{n}$. We let
$\mathbf{S}^{\prime}=\mathbf{S}\cup\\{A_{1},\ldots,A_{n}\\}$, where
$A_{1},\ldots,A_{n}$ are fresh unary predicates. Let $q^{\prime}(\bar{x})$ be
the UCQ that results from $q(\bar{x})$ by adding the conjunction
$A_{1}(x_{1})\wedge\cdots\wedge A_{n}(x_{n})$ to every disjunct of
$q(\bar{x})$. Let
$Q^{\prime}={(\mathbf{S}^{\prime},\mathcal{O},\exists\bar{x}\,q^{\prime}(\bar{x}))}$.
It is not hard to check that $Q$ is FO-rewritable iff $Q^{\prime}$ is.

Indeed, if $\varphi_{Q}(x_{1},\ldots,x_{n})$ is an FO-rewriting of $Q$, then
$\exists x_{1},\ldots,x_{n}\,(\varphi_{Q}(x_{1},\ldots,x_{n})\wedge
A_{1}(x_{1})\wedge\cdots\wedge A_{n}(x_{n}))$ is one of $Q^{\prime}$.

Conversely, if $Q^{\prime}$ is FO-rewritable then there is a Boolean UCQ
$p^{\prime}$ that is equivalent to $Q^{\prime}$. Now, for any
$\mathbf{S}^{\prime}$-database $\mathfrak{D}$, $\mathfrak{D}\models
q^{\prime}$ iff there are $a_{1},\ldots,a_{n}\in\mathsf{adom}(\mathfrak{D})$
such that $A_{1}(a_{1}),\ldots,A_{n}(a_{n})\in\mathfrak{D}$ and
$\mathfrak{D}\models Q(a_{1},\ldots,a_{n})$. Let $p$ be the UCQ that results
from $p^{\prime}$ by removing all occurrences of $A_{i}(x_{i})$ and the
associated existential quantifier $\exists x_{i}$. It is easy to see that $p$
is a UCQ-rewriting of $Q$.

Now consider an OMQ $Q={(\mathbf{S},\mathcal{O},q)}$ from
${(\mathsf{FG},\mathsf{UBCQ})}$. In a first step, we transform $Q$ into an
equivalent OMQ $Q^{\prime}$ that falls in ${(\mathsf{FG},\mathsf{AQ}_{0})}$.
This is easy: we simply choose a fresh predicate $G$ of arity zero and add to
$\mathcal{O}$ the rules $p\rightarrow G$ for every disjunct $p$ of $q$. Notice
that $\mathcal{O}$ is still frontier-guarded, since $q$ is Boolean. Call the
resulting ontology $\mathcal{O}^{\prime}$, i.e.,
$Q^{\prime}={(\mathbf{S},\mathcal{O}^{\prime},G)}$.

Now we choose a fresh predicate $C$ of arity $0pt{\mathcal{O}^{\prime}}$. We
then construct the OMQ $\eta_{C}(Q^{\prime})$ that has data schema
$\mathbf{S}\cup\\{C\\}$. This translation takes exponential time, and the
ontology of $\eta_{C}(Q^{\prime})$ may be of exponential size. However, as
already mentioned in the main body of the paper, the arity of each predicate
occurring in $\eta_{C}(Q^{\prime})$ is at most $0pt{\mathcal{O}^{\prime}}$.

The OMQ $\eta_{C}(Q^{\prime})$ falls in ${(\mathsf{G},\mathsf{AQ}_{0})}$. We
can, according to Theorem 9, decide FO-rewritability for that class in
2ExpTime, with a double exponential dependence only on the width of the data
schema. Since $0pt{\mathbf{S}\cup\\{C\\}}=0pt{\mathcal{O}^{\prime}}$, it
follows that FO-rewritability of $\eta_{C}(Q^{\prime})$ can be decided in
2ExpTime, where the second exponent of the run-time depends on
$0pt{\mathcal{O}^{\prime}}$ only. Hence, we can decide whether
$\eta_{C}(Q^{\prime})$ if FO-rewritable in 2ExpTime. Given that the
construction of $\eta_{C}(Q^{\prime})$ (starting with $Q$) is, of course, also
feasibly in 2ExpTime, the fact that
$\mathsf{FORew(\mathsf{FG},\mathsf{UBCQ})}$ is in 2ExpTime follows by Lemma
25. Using Lemma 28, we obtain that $\mathsf{FORew(\mathsf{FG},\mathsf{UCQ})}$
is in 2ExpTime as well.