CNRS, DI ENS, École normale supérieure, Université PSL, Paris, Francechien-
<EMAIL_ADDRESS>Paris Cité, CNRS, IRIF, F-75013, Paris, France
MINES ParisTech, Université PSL, F-75006, Paris, Francefrancois.sellier@mines-
paristech.fr [500]Theory of computation Streaming, sublinear and near linear
time algorithms [500]Theory of computation Approximation algorithms analysis A
previous version of this work appeared at ESA 2022.111The conference version
[14] does not contain some proofs, nor the examples mentioned in the
introduction or the more general setting of streaming with irrelevant edges
that is presented in the appendix here. This work was funded by the grants
ANR-19-CE48-0016 and ANR-18-CE40-0025-01 from the French National Research
Agency (ANR).

# Maximum Weight $b$-Matchings in Random-Order Streams

Chien-Chung Huang  François Sellier

###### Abstract

We consider the maximum weight $b$-matching problem in the random-order semi-
streaming model. Assuming all weights are small integers drawn from $[1,W]$,
we present a $2-\frac{1}{2W}+\varepsilon$ approximation algorithm, using a
memory of $O(\max(|M_{G}|,n)\cdot poly(\log(m),W,1/\varepsilon))$, where
$|M_{G}|$ denotes the cardinality of the optimal matching. Our result
generalizes that of Bernstein [3], which achieves a $3/2+\varepsilon$
approximation for the maximum cardinality simple matching. When $W$ is small,
our result also improves upon that of Gamlath _et al._ [11], which obtains a
$2-\delta$ approximation (for some small constant $\delta\sim 10^{-17}$) for
the maximum weight simple matching. In particular, for the weighted
$b$-matching problem, ours is the first result beating the approximation ratio
of $2$. Our technique hinges on a generalized weighted version of edge-degree
constrained subgraphs, originally developed by Bernstein and Stein [5]. Such a
subgraph has bounded vertex degree (hence uses only a small number of edges),
and can be easily computed. The fact that it contains a
$2-\frac{1}{2W}+\varepsilon$ approximation of the maximum weight matching is
proved using the classical Kőnig-Egerváry’s duality theorem.

###### keywords:

Maximum weight matching, $b$-matching, streaming, random order

##  1 Introduction

The maximum weight ($b$-)matching problem is a classical problem in
combinatorial optimization. In this paper we will study a sparsifier for that
problem and use it in order to design a streaming algorithm for randomly-
ordered streams of edges.

Our main tool is a generalized weighted version of the _edge-degree
constrained subgraph_ (EDCS), a graph sparsifier originally designed for the
maximum matching problem by Bernstein and Stein [5]. Let us first recall the
definition an EDCS $H$ of a graph $G$ [5].

######  Definition 1.1 (from [5]).

Let $G=(V,E)$ be a graph, and $H$ a subgraph of $G$. Given any integer
parameters $\beta\geq 2$ and $\beta^{-}\leq\beta-1$, we say that $H$ is a
$(\beta,\beta^{-})$-EDCS of $G$ if $H$ satisfies the following properties:

  1. (i)

For any edge $(u,v)\in H$, $\deg_{H}(u)+\deg_{H}(v)\leq\beta$

  2. (ii)

For any edge $(u,v)\in G\backslash H$, $\deg_{H}(u)+\deg_{H}(v)\geq\beta^{-}$.

An EDCS has a size that can be easily controlled by the parameter $\beta$ and
it somehow “balances” the vertex degrees in the graph. A very nice property of
this sparsifier is that, for well-chosen values of $\beta$ and $\beta^{-}$, it
always contains a $3/2+\varepsilon$ approximation of the maximum cardinality
matching [2, 6]:

######  Theorem 1.2 (from the recent work of Assadi and Bernstein [2]).

Let $0<\varepsilon<1/2$. Set $\lambda=\frac{\varepsilon}{32}$. Let
$\beta\geq\beta^{-}+1$ be integers such that $\beta\geq
8\lambda^{-2}\log(1/\lambda)$ and $\beta^{-}\geq(1-\lambda)\cdot\beta$. Then
any $(\beta,\beta^{-})$-EDCS $H$ of a graph $G$ contains a matching $M_{H}$
such that $\left(\frac{3}{2}+\varepsilon\right)\cdot|M_{H}|\geq|M_{G}|$ where
$M_{G}$ denotes the maximum cardinality matching.

In our paper, we generalize the EDCS in two ways:

  * •

we handle (small) integer-weighted edges;

  * •

we handle the more general case of $b$-matchings.

To describe our generalization, first let us introduce some notation. A
weighted multi-graph $G=(V,E)$ is defined by its set of vertices $V$ and its
multi-set of weighted edges $E$ drawn from $V\times V\times\\{1,2,\dots,W\\}$
(_i.e._ , $e=(u,v,k)$ represents an edge between $u$ and $v$ of weight
$w(e)=k$). We emphasize that $E$ is a multi-set: not only can there be
multiple edges between two vertices, but also some of these edges can have the
same weight. We assume that the multi-graph does not contain any self-loop.
For a given vertex $v\in V$ and a given subgraph $H$ of $G$, $\delta_{H}(v)$
denotes the multi-set of incident edges to $v$ in $H$, $\deg_{H}(v)$ the
_degree_ of $v$ in the multi-graph $H$ and $\mathrm{\mathbf{w}\\!\deg}_{H}(v)$
its _weighted degree_ $\sum_{(u,v,w)\in\delta_{H}(v)}w$ in $H$. Given a
weighted multi-graph $G=(V,E)$ and a set of capacities
$b_{v}\in\mathbb{Z}_{+}$ associated to each vertex $v\in V$, a multi-set of
weighted edges $M$ is called a _$b$ -matching_ if for all $v\in V$ the number
of edges incident to $v$ in $M$ is smaller than or equal to $b_{v}$. For a
given subgraph $H$ of $G$, we denote by $M_{H}$ an arbitrary maximum weight
$b$-matching included in $H$. The concept of $b$-matching encompasses that of
matching and allows us to tackle a larger variety of real situations where the
vertices have different capacities, _e.g._ [21]. In this paper we will assume
that the number of edges between any two vertices $u$ and $v$ is at most
$\min(b_{u},b_{v})$.222This is actually a reasonable assumption as the maximum
number of edges that are relevant between two given vertices $u$ and $v$ to
construct a $b$-matching is at most $\min(b_{u},b_{v})$. This assumption is
more debatable in the streaming setting, and this is why we explain how to
handle this case in Appendix D.

######  Definition 1.3.

Let $G=(V,E)$ be a weighted multi-graph, $\\{b_{v}\\}_{v\in V}$ be a set of
constraints, and $H$ be a subgraph of $G$. Given any integer parameters
$\beta\geq 3$ and $\beta^{-}\leq\beta-2$, we say that $H$ is a
$(\beta,\beta^{-})$-$w$-$b$-EDCS of $G$ if $H$ satisfies the following
properties:

  1. (i)

For any edge $(u,v,w_{uv})\in H$,
$\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(u)}{b_{u}}+\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(v)}{b_{v}}\leq\beta\cdot
w_{uv}$

  2. (ii)

For any edge $(u,v,w_{uv})\in G\backslash H$,
$\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(u)}{b_{u}}+\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(v)}{b_{v}}\geq\beta^{-}\cdot
w_{uv}$.

An EDCS is a spacial case of a _weighted $b$-EDCS_ when all the $b_{v}$s and
all the weights are equal to $1$. We can show that such $w$-$b$-EDCSes as
described in Definition 1.3 always exist. Moreover, we can also prove that it
uses only a reasonable number of edges (up to $2\beta\cdot|M_{G}|$) and that a
relatively large weighted $b$-matching can be found in it:

######  Theorem 1.4.

Let $0<\varepsilon<1/2$ and let $W$ be an integer parameter. Set
$\lambda=\frac{\varepsilon}{100W}$. Let $\beta\geq\beta^{-}+2$ be integers
such that $\frac{\beta+6W}{\log(\beta+6W)}\geq 2W^{2}\lambda^{-2}$ and
$\beta^{-}-6W\geq(1-\lambda)\cdot(\beta+6W)$. Then any
$(\beta,\beta^{-})$-$w$-$b$-EDCS $H$ of an edge-weighted multi-graph $G$ with
integer edge weights bounded by $W$ contains a $b$-matching $M_{H}$ such that
$\left(2-\frac{1}{2W}+\varepsilon\right)\cdot w(M_{H})\geq w(M_{G})$.

Moreover, in Appendix B, we give a whole class of tight examples reaching the
bound of Theorem 1.4. Comparing with the previous result of [2, 6] (Theorem
1.2), setting $W=1$, we can observe that the approximation ratio is the same,
even though the constraints on $\beta$ and $\beta^{-}$ are a bit stricter
here. However, in our case we can deal with $b$-matchings as well, and we can
handle situations when $W>1$.

The _semi-streaming_ model of computation [10] has been motivated by the
recent rise of massive graphs, for which we cannot afford to store all the
edges in memory while it is still achievable to store an output of the
considered problem in memory. Given that the graph is made of $|V|=n$ vertices
and $|E|=m$ edges, in the semi-streaming model the graph is presented to the
algorithm as a stream of edges $e_{1},\ldots,e_{m}$. The algorithm is allowed
to make a single pass over that stream and can use a memory roughly
proportional to the output size (up to a poly-logarithmic factor).

We note that in the most general model where an adversary decides the order
the elements, even for the maximum cardinality simple matching, it is still
unclear whether it is possible to beat the approximation ratio of $2$.

Our focus here is on the _random-order_ streaming model, where the permutation
of the edges in the stream is assumed to be chosen uniformly at random. This
is a quite reasonable assumption as real-world data have little reason of
being ordered in an adversarial way. In particular, for this model, there are
evidence that it is possible to beat the approximation factor of $2$ [18, 11],
at least for the simple matching.

Using an adaptation of EDCS, Bernstein [3] obtained a $3/2+\varepsilon$
approximation in the random-order semi-streaming framework (with probability
$1-2n^{-3}$ and using $O(n\cdot\log(n)\cdot poly(1/\varepsilon))$ memory).
Similarly, we can adapt our $w$-$b$-EDCSes to design a semi-streaming
algorithm for randomly-ordered streams of weighted edges:

######  Theorem 1.5.

Let $0<\varepsilon<\frac{1}{2}$ and let $W$ be an integer parameter. There
exists an algorithm that can extract with high probability (at least
$1-2m^{-3}$) from a randomly-ordered stream of weighted edges having integer
weights in $\\{1,\ldots,W\\}$ a weighted $b$-matching with an approximation
ratio of $2-\frac{1}{2W}+\varepsilon$, using $O(\max(|M_{G}|,n)\cdot
poly(\log(m),W,1/\varepsilon))$ memory.

Theorem 1.5 is the first result for the maximum (integer-weighted)
$b$-matching problem in the random-order semi-streaming framework. For the
special case of simple matching, when $W=1$, we essentially re-capture the
result of Bernstein [3] (albeit using slightly more memory). When $W>1$, we
note that prior to our work, Gamlath _et al._ [11] have obtained an
approximation ratio of $2-\delta$ for some small $\delta\sim 10^{-17}$. Our
result gives a better approximation when $W$ is reasonably small (but using a
memory depending polynomially in $W$) and we believe that our approach is
significantly simpler.

######  Remark 1.6.

Another generalization of EDCS has been developed by Bernstein _et al._ [4] to
maintain a $3/2+\varepsilon$ approximation of the optimal weighted matching in
a dynamic graph. However it is still unknown if their construction can
actually lead to an algorithm in the random-order one-pass semi-streaming
model [4], or applied to $b$-matchings.

#### Technical Overview

To generalize the EDCS to the weighted case, a very natural first idea is to
build multiple EDCSes, one for each edge-weight from $1$ to $W$, and then take
their union. We show in Appendix C that such an idea does not lead to a
subgraph containing a matching that is better than a $2$ approximation.

Our approach is a proper generalization of EDCS, as defined in Definition 3.1.
In Theorem 1.4, we show that such a $w$-$b$-EDCS contains a matching of good
approximation ratio. The proof of this theorem is technically the most
innovative part of the present work. In order to handle integer-weighted
matchings (see Section 2) we use Kőnig-Egerváry’s duality theorem [7] and the
construction of an auxiliary graph. The fact that the weights of the edges are
integers is critical to get an approximation ratio better than $2$ (especially
for Claim 1). Then, to handle $b$-matchings (see Section 3), we build a
reduction to simple matchings and show that by doing so we do not lose too
much in the approximation ratio.

Regarding Theorem 1.5, when we design a semi-streaming algorithm to extract a
$b$-matching there is an additional challenge: we do not know in advance the
actual size of $M_{G}$, which cannot be bounded by $n$ (for instance $|M_{G}|$
could be of size $n^{1.2}$ or even larger), but we still want to use as little
memory as possible, _i.e._ $O(\max(|M_{G}|,n)\cdot
poly(\log(m),W,1/\varepsilon))$. We tackle this issue using a guessing
technique in the early phase of the stream (see Section 4).

#### Related Work

In the adversarial semi-steaming setting, for the unweighted case, the simple
greedy algorithm building a maximal matching provides a $2$ approximation,
which is the best known approximation ratio. Knowing whether it is possible to
achieve a better approximation ratio is a major open question in the field of
streaming algorithms. For weighted matchings an approximation ratio of
$2+\varepsilon$ can be achieved [12, 19, 20]. For weighted $b$-matchings the
approximation ratio $2+\varepsilon$ can also be attained [15]. On the hardness
side, we know that an approximation ratio better than $1+\ln 2\approx 1.69$
cannot be achieved [16].

In contrast, for the _random-order_ stream, a first result was obtained by
Konrad, Magniez, and Mathieu [18] with an approximation ratio strictly below
$2$ for unweighted simple matchings. The approximation ratio was then improved
in a sequence of papers [11, 17, 9, 3]. Currently the best result is due to
Assadi and Behnezhad [1], who obtained the ratio of $3/2-\delta$ for some
small constant $\delta\sim 10^{-14}$. Regarding weighted simple matchings,
Gamlath _et al._ [11] obtained an approximation ratio of $2-\delta$ for some
small constant $\delta\sim 10^{-17}$. Regarding $b$-matchings, to our
knowledge the only result is an approximation ratio of $2-\delta$ _in
expectation_ for random-order online matroid intersection by Guruganesh and
Singla [13] (hence it applies for unweighted bipartite $b$-matchings).

##  2 EDCS for Weighted Matchings

In this section we consider the problem of finding a maximum weight matching
in an edge-weighted graph $G=(V,E)$ where the edges have integer weights in
$[1,W]$. For ease of presentation, we will use simplified notations for
_simple_ graphs in this section. Here $w(u,v)$ denotes edge weight between
vertices $u$ and $v$. For a subgraph $H$ of $G$ and a vertex $u\in V$, we
denote by $N_{H}(v)$ the set of vertices adjacent to $v$ in $H$, by
$\deg_{H}(v)$ the degree of $v$ in $H$, _i.e._ , $\deg_{H}(v)=|N_{H}(v)|$, and
by $\mathrm{\mathbf{w}\\!\deg}_{H}(v)$ the weighted degree of $v$ in $H$,
_i.e._ , $\mathrm{\mathbf{w}\\!\deg}_{H}(v)=\sum_{u\in N_{H}(v)}w(u,v)$. For a
subgraph $H$ of $G$, we will denote by $M_{H}$ an arbitrary maximum weight
matching in $H$. Then we define the notion of edge-degree constrained
subgraphs for weighted graphs ($w$-EDCS), which in fact is just Definition 1.3
specialized to the setting in this section.

######  Definition 2.1.

Let $G=(V,E)$ be a graph with weighted edges, and $H$ be a subgraph of $G$.
Given any integer parameters $\beta\geq 3$ and $\beta^{-}\leq\beta-2$, we say
that $H$ is a $(\beta,\beta^{-})$-$w$-EDCS of $G$ if $H$ satisfies the
following properties:

  1. (i)

For any edge $(u,v)\in H$,
$\mathrm{\mathbf{w}\\!\deg}_{H}(u)+\mathrm{\mathbf{w}\\!\deg}_{H}(v)\leq\beta\cdot
w(u,v)$

  2. (ii)

For any edge $(u,v)\in G\backslash H$,
$\mathrm{\mathbf{w}\\!\deg}_{H}(u)+\mathrm{\mathbf{w}\\!\deg}_{H}(v)\geq\beta^{-}\cdot
w(u,v)$.

Here is a first simple proposition on $(\beta,\beta^{-})$-$w$-EDCS (coming
from Property (i)).

######  Proposition 2.2.

Let $H$ be a $(\beta,\beta^{-})$-$w$-EDCS of a given graph $G$. Then, for all
$v\in V$, we have $\deg_{H}(v)\leq\beta$.

######  Proof 2.3.

Let $v\in V$. If $N_{H}(v)=\emptyset$, the stated property is trivial.
Otherwise, pick a vertex $u$ such that $w(u,v)=\min_{u^{\prime}\in
N_{H}(v)}w(u^{\prime},v)$. Then, by Property (i), $\beta\cdot
w(u,v)\geq\mathrm{\mathbf{w}\\!\deg}_{H}(v)$. Therefore,
$\deg_{H}(v)\leq\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(v)}{w(u,v)}\leq\beta$, as
any edge incident to $v$ in $H$ has a weight larger or equal to $w(u,v)$.

We show the existence of $w$-EDCSes by construction, using a local search
algorithm. The following proof closely follows the argument of [2].

######  Proposition 2.4.

Any graph $G=(V,E)$ with weighted edges contains a
$(\beta,\beta^{-})$-$w$-EDCS for any parameters $\beta\geq\beta^{-}+2$. Such a
$(\beta,\beta^{-})$-$w$-EDCS can be found in $O(\beta^{2}W^{2}\cdot n)$ time.

######  Proof 2.5.

Start with an empty subgraph $H$. Then try the following local improvements of
$H$, until it is no longer possible. If there is an edge in $H$ violating
Property (i) of Definition 2.1, then fix that edge by removing it from $H$.
Otherwise, if there is an edge in $G\backslash H$ violating Property (ii),
then fix that edge by inserting it in $H$.

Observe that we give the priority to the correction of violations of Property
(i), so that at each step of the algorithm all the vertices have degrees
bounded by $\beta+1$ (as after inserting an edge, Proposition 2.2 may be
violated). To prove that this algorithm terminates in finite time and to show
the existence of a $w$-EDCS, we introduce a potential function:

$\Phi(H)=(2\beta-2)\sum_{(u,v)\in H}w(u,v)^{2}-\sum_{u\in
V}(\mathrm{\mathbf{w}\\!\deg}_{H}(u))^{2}.$

As the vertices have degrees bounded by $\beta+1$ and the edges have weights
bounded by $W$, the value of that potential function is bounded by
$2\beta^{2}W^{2}\cdot n$. Then we can show that after each local improvement
step, the value of $\Phi(H)$ increases at least by $2$.

In fact, when Property (i) is not respected by some edge $(u,v)\in H$, we have
$\mathrm{\mathbf{w}\\!\deg}_{H}(u)+\mathrm{\mathbf{w}\\!\deg}_{H}(v)\geq\beta\cdot
w(u,v)+1$. If we fix it by erasing this edge from $H$ the value of $\Phi(H)$
is increased by $-(2\beta-2)\cdot
w(u,v)^{2}+2\cdot\mathrm{\mathbf{w}\\!\deg}_{H}(u)\cdot
w(u,v)+2\cdot\mathrm{\mathbf{w}\\!\deg}_{H}(v)\cdot w(u,v)-2\cdot
w(u,v)^{2}\geq-(2\beta-2)\cdot w(u,v)^{2}+2\cdot(\beta\cdot w(u,v)+1)\cdot
w(u,v)-2\cdot w(u,v)^{2}=2\cdot w(u,v)\geq 2$.

When Property (ii) is not respected by some edge $(u,v)\in G\backslash H$, we
have
$\mathrm{\mathbf{w}\\!\deg}_{H}(u)+\mathrm{\mathbf{w}\\!\deg}_{H}(v)\leq\beta^{-}\cdot
w(u,v)-1$. If we insert $(u,v)$ in $H$, the value of $\Phi(H)$ increases by
$(2\beta-2)\cdot w(u,v)^{2}-2\cdot\mathrm{\mathbf{w}\\!\deg}_{H}(u)\cdot
w(u,v)-2\cdot\mathrm{\mathbf{w}\\!\deg}_{H}(v)\cdot w(u,v)-2\cdot
w(u,v)^{2}\geq(2\beta-2)\cdot w(u,v)^{2}-2\cdot(\beta^{-}\cdot w(u,v)-1)\cdot
w(u,v)-2\cdot w(u,v)^{2}\geq(2\cdot(\beta-\beta^{-})-4)\cdot w(u,v)^{2}+2\cdot
w(u,v)\geq 2\cdot w(u,v)\geq 2$, as $\beta\geq\beta^{-}+2$.

Therefore, the algorithm terminates in $O(\beta^{2}W^{2}\cdot n)$ steps.

We also introduce the notion of $w$-vertex-cover of the edge-weighted graph.

######  Definition 2.6.

We say that the non-negative integer variables $(\alpha_{v})_{v\in V}$
represent a $w$-vertex-cover of a subgraph $H$ of $G$ if for all $(u,v)\in H$,
we have $w(u,v)\leq\alpha_{u}+\alpha_{v}$. The sum $\sum_{v\in V}\alpha_{v}$
is called the weight of the $w$-vertex-cover.

To use this data structure for the maximum weight problem, we will use the
theorem of Kőnig-Egerváry [7], which is a classic duality theorem.

######  Theorem 2.7 (Kőnig-Egerváry).

In any edge-weighted bipartite subgraph $H$ of $G$, the maximum weight of a
matching equals the smallest weight of a $w$-vertex-cover.

This theorem allows us to prove the following lemma, which is technically the
most important part of the present work.

######  Lemma 2.8.

Let $0<\varepsilon<1/2$ and $W$ be an integer parameter. For
$\beta\geq\beta^{-}+2$ integers such that $\frac{\beta}{\beta^{-}}\leq
1+\frac{\varepsilon}{5W}$ and $\beta^{-}\geq\frac{4W}{\varepsilon}$, we have
that any $(\beta,\beta^{-})$-$w$-EDCS $H$ of a bipartite graph $G$ (with
integer edge weights bounded by $W$) contains a matching $M_{H}$ such that
$\left(2-\frac{1}{2W}+\varepsilon\right)\cdot w(M_{H})\geq w(M_{G})$.

######  Proof 2.9.

Using Kőnig-Egerváry’s theorem in the bipartite graph $H$, we know that there
exist integers $(\alpha_{v})_{v\in V}$ such that:

  * •

$\sum_{v\in V}\alpha_{v}=w(M_{H})$

  * •

for all $(u,v)\in H$, $w(u,v)\leq\alpha_{u}+\alpha_{v}$

Now consider the optimal matching $M_{G}$ in $G$. The first idea is to use the
duality theorem to relate $w(M_{G})$ to $w(M_{H})$, with a leftover term that
will be analyzed in the second part of the proof. We introduce the notion of
_good_ and _bad_ edges:

  * •

the edges $(u,v)\in M_{G}$ such that $\beta^{-}\cdot
w(u,v)\leq\beta\cdot(\alpha_{u}+\alpha_{v})$, which are called _good edges_ ;
the set of good edges is denoted as $M_{good}$

  * •

the edges $(u,v)\in M_{G}$ such that $\beta^{-}\cdot
w(u,v)>\beta\cdot(\alpha_{u}+\alpha_{v})$, which are called _bad edges_ ; the
set of bad edges is denoted as $M_{bad}$

A key observation is that the edges in $M_{G}\cap H$ are necessarily good
edges by the definition of the $w$-vertex-cover $(\alpha_{v})_{v\in V}$ and
the fact that $\beta^{-}<\beta$. Therefore, the bad edges $(u,v)$ are in
$G\backslash H$ and as a consequence they satisfy Property (ii) of Definition
2.1, _i.e._ $\beta^{-}\cdot
w(u,v)\leq\mathrm{\mathbf{w}\\!\deg}_{H}(u)+\mathrm{\mathbf{w}\\!\deg}_{H}(v)$.

Hence we can write the following:

$\displaystyle\beta^{-}$ $\displaystyle\cdot w(M_{G})=\sum_{(u,v)\in
M_{good}}\beta^{-}\cdot w(u,v)+\sum_{(u,v)\in M_{bad}}\beta^{-}\cdot w(u,v)$
$\displaystyle\leq\sum_{(u,v)\in
M_{good}}\beta\cdot(\alpha_{u}+\alpha_{v})+\sum_{(u,v)\in
M_{bad}}(\mathrm{\mathbf{w}\\!\deg}_{H}(u)+\mathrm{\mathbf{w}\\!\deg}_{H}(v))$
$\displaystyle=\sum_{(u,v)\in
M_{G}}\beta\cdot(\alpha_{u}+\alpha_{v})+\sum_{(u,v)\in
M_{bad}}(\mathrm{\mathbf{w}\\!\deg}_{H}(u)+\mathrm{\mathbf{w}\\!\deg}_{H}(v)-\beta\cdot(\alpha_{u}+\alpha_{v}))$
$\displaystyle\leq\beta\cdot w(M_{H})+\sum_{(u,v)\in
M_{bad}}((\mathrm{\mathbf{w}\\!\deg}_{H}(u)-\beta\cdot\alpha_{u})_{+}+(\mathrm{\mathbf{w}\\!\deg}_{H}(v)-\beta\cdot\alpha_{v})_{+}),$

where $(x)_{+}$ denotes the non-negative part $\max(x,0)$. In the last
inequality we also used the fact that $\sum_{(u,v)\in
M_{G}}(\alpha_{u}+\alpha_{v})\leq\sum_{v\in V}\alpha_{v}=w(M_{H})$, as each
vertex of $V$ is counted at most once in that sum. Now, denoting by $V_{bad}$
the set of vertices which are the endpoints of a bad edge and such that
$\mathrm{\mathbf{w}\\!\deg}_{H}(u)-\beta\cdot\alpha_{u}>0$, we get

$\beta^{-}\cdot w(M_{G})\leq\beta\cdot w(M_{H})+\sum_{v\in
V_{bad}}(\mathrm{\mathbf{w}\\!\deg}_{H}(v)-\beta\cdot\alpha_{v}).$ (1)

Naturally, we want to upper-bound the value of $\sum_{v\in
V_{bad}}(\mathrm{\mathbf{w}\\!\deg}_{H}(v)-\beta\cdot\alpha_{v})$ and we will
do so _via_ a specially-constructed graph. Before we describe this graph, we
can first easily observe that for any $v\in V_{bad}$, for any $u\in N_{H}(v)$,
we have $w(u,v)\geq\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(v)}{\beta}>\alpha_{v}$
(by Property (i) of Definition 2.1 and the definition of $V_{bad}$); moreover,
as $(\alpha_{v})_{v\in V}$ is a $w$-vertex-cover of $H$, we obtain that
$\alpha_{u}>0$. These observations will be useful in the following.

The new graph is $H_{bad}=(V_{bad}\cup\tilde{V},\tilde{E})$. The vertices in
$H_{bad}$ are the vertices of $V_{bad}$ as well as copies of the vertices of
$V$ such that $\alpha_{v}>0$, _i.e._ $\tilde{V}=\\{\tilde{v}:v\in
V,\alpha_{v}>0\\}$. We build the set of edges $\tilde{E}$ as follows. For each
$v\in V_{bad}$, for each $u\in N_{H}(v)$, we create in $\tilde{E}$ an edge
$(v,\tilde{u})$ such that $w(v,\tilde{u})=w(v,u)-\alpha_{v}$ (note that if $u$
is also in $V_{bad}$, then $\tilde{E}$ will also contain another edge
$(u,\tilde{v})$ such that $w(u,\tilde{v})=w(u,v)-\alpha_{u}$). Note that
$w(v,\tilde{u})\in\mathbb{Z}_{>0}$, since $w(u,v)>\alpha_{v}$ as observed
above. Therefore the graph $H_{bad}$ still has non-negative integer-valued
edge weights. We next remove some edges from $\tilde{E}$: while there exists a
vertex $v\in V_{bad}$ such that
$\mathrm{\mathbf{w}\\!\deg}_{H_{bad}}(v)>\mathrm{\mathbf{w}\\!\deg}_{H}(v)-\beta\cdot\alpha_{v}+W$,
we pick an arbitrary edge $(v,\tilde{u})\in\tilde{E}$ incident to $v$ and
remove it from $H_{bad}$. This process guarantees the following property:

$\forall v\in
V_{bad},\mathrm{\mathbf{w}\\!\deg}_{H}(v)-\beta\cdot\alpha_{v}\leq\mathrm{\mathbf{w}\\!\deg}_{H_{bad}}(v)\leq\mathrm{\mathbf{w}\\!\deg}_{H}(v)-\beta\cdot\alpha_{v}+W.$
(2)

This finishes the description of the graph $H_{bad}$. By (2), for any
$(v,\tilde{u})\in\tilde{E}$ we have:

$\displaystyle\beta\cdot w(v,\tilde{u})+W=\beta\cdot(w(v,u)-\alpha_{v})+W$
$\displaystyle\geq\mathrm{\mathbf{w}\\!\deg}_{H}(v)-\beta\cdot\alpha_{v}+W+\mathrm{\mathbf{w}\\!\deg}_{H}(u)$
$\displaystyle\geq\mathrm{\mathbf{w}\\!\deg}_{H_{bad}}(v)+\mathrm{\mathbf{w}\\!\deg}_{H_{bad}}(\tilde{u}).$

Summing this inequality over all the edges in $\tilde{E}$ we obtain:

$\displaystyle\beta$ $\displaystyle\cdot
w(\tilde{E})+W\cdot|\tilde{E}|\geq\sum_{(v,\tilde{u})\in\tilde{E}}(\mathrm{\mathbf{w}\\!\deg}_{H_{bad}}(v)+\mathrm{\mathbf{w}\\!\deg}_{H_{bad}}(\tilde{u}))$
$\displaystyle=\sum_{v\in
V_{bad}}\deg_{H_{bad}}(v)\cdot\mathrm{\mathbf{w}\\!\deg}_{H_{bad}}(v)+\sum_{\tilde{u}\in\tilde{V}}\deg_{H_{bad}}(\tilde{u})\cdot\mathrm{\mathbf{w}\\!\deg}_{H_{bad}}(\tilde{u})$
$\displaystyle\geq\sum_{v\in
V_{bad}}\frac{\mathrm{\mathbf{w}\\!\deg}_{H_{bad}}(v)}{W}\cdot\mathrm{\mathbf{w}\\!\deg}_{H_{bad}}(v)+\sum_{\tilde{u}\in\tilde{V}}\frac{\mathrm{\mathbf{w}\\!\deg}_{H_{bad}}(\tilde{u})}{\alpha_{u}}\cdot\mathrm{\mathbf{w}\\!\deg}_{H_{bad}}(\tilde{u})$
$\displaystyle=\sum_{v\in
V_{bad}}\frac{(\mathrm{\mathbf{w}\\!\deg}_{H_{bad}}(v))^{2}}{W}+\sum_{\tilde{u}\in\tilde{V}}\frac{(\mathrm{\mathbf{w}\\!\deg}_{H_{bad}}(\tilde{u}))^{2}}{\alpha_{u}}$
$\displaystyle\geq\sum_{v\in
V_{bad}}\frac{1}{W}\cdot\left(\frac{w(\tilde{E})}{|V_{bad}|}\right)^{2}+\sum_{\tilde{u}\in\tilde{V}}\frac{1}{\alpha_{u}}\cdot\left(\frac{w(\tilde{E})\cdot\alpha_{u}}{\sum_{\tilde{u}^{\prime}\in\tilde{V}}\alpha_{u^{\prime}}}\right)^{2}$
$\displaystyle=\frac{w(\tilde{E})^{2}}{W\cdot|V_{bad}|}+\frac{w(\tilde{E})^{2}}{\sum_{\tilde{u}^{\prime}\in\tilde{V}}\alpha_{u^{\prime}}}.$

The second inequality comes from the fact that the degree of a vertex can be
lower-bounded by the weighted degree of that vertex divided by the weight of
the largest edge incident to it (for $v\in V_{bad}$ this weight is $W$, and
for $\tilde{u}\in\tilde{V}$ it is $\alpha_{u}$, as
$w(v,\tilde{u})=w(v,u)-\alpha_{v}\leq\alpha_{u}$ for $v$ adjacent to
$\tilde{u}$ in $H_{bad}$). The third inequality comes from the minimization of
the function over the constraints $\sum_{v\in
V_{bad}}\mathrm{\mathbf{w}\\!\deg}_{H_{bad}}(v)=\sum_{\tilde{u}\in\tilde{V}}\mathrm{\mathbf{w}\\!\deg}_{H_{bad}}(\tilde{u})=w(\tilde{E})$.
Then we get

$\beta+W\geq\frac{w(\tilde{E})}{W\cdot|V_{bad}|}+\frac{w(\tilde{E})}{\sum_{\tilde{u}\in\tilde{V}}\alpha_{u}}.$
(3)

The following claim will help us lower bound the average weighted degree of
the vertices of $V_{bad}$ in $H_{bad}$, namely, $w(\tilde{E})/|V_{bad}|$. For
this part it is crucial that the weights are integers.

######  Claim 1.

For all $(u,v)\in M_{bad}$,
$(\mathrm{\mathbf{w}\\!\deg}_{H}(u)-\beta\cdot\alpha_{u})_{+}+(\mathrm{\mathbf{w}\\!\deg}_{H}(v)-\beta\cdot\alpha_{v})_{+}\geq\frac{\beta^{-}}{1+\varepsilon/4}$

We proceed by contradiction. Suppose that there exists $(u,v)\in M_{bad}$ such
that
$(\mathrm{\mathbf{w}\\!\deg}_{H}(u)-\beta\cdot\alpha_{u})_{+}+(\mathrm{\mathbf{w}\\!\deg}_{H}(v)-\beta\cdot\alpha_{v})_{+}<\frac{\beta^{-}}{1+\varepsilon/4}$.
Then, as $\beta^{-}\cdot
w(u,v)\leq\beta\cdot(\alpha_{u}+\alpha_{v})+(\mathrm{\mathbf{w}\\!\deg}_{H}(u)-\beta\cdot\alpha_{u})_{+}+(\mathrm{\mathbf{w}\\!\deg}_{H}(v)-\beta\cdot\alpha_{v})_{+}$,
it means that

$\beta\cdot(\alpha_{u}+\alpha_{v})<\beta^{-}\cdot
w(u,v)<\beta\cdot(\alpha_{u}+\alpha_{v})+\frac{\beta^{-}}{1+\varepsilon/4},$

and therefore by dividing by $\beta^{-}$ we obtain

$\frac{\beta}{\beta^{-}}\cdot(\alpha_{u}+\alpha_{v})<w(u,v)<\frac{\beta}{\beta^{-}}\cdot(\alpha_{u}+\alpha_{v})+\frac{1}{1+\varepsilon/4}.$

As $(\alpha_{u}+\alpha_{v})\in\\{0,1,\dots,W\\}$ (recall that $(u,v)$ is a bad
edge) and because $\frac{\beta}{\beta^{-}}\leq
1+\frac{\varepsilon}{5W}<1+\frac{\varepsilon}{4W\cdot(1+\varepsilon/4)}$,
there cannot be any integer in the open interval

$\left]\frac{\beta}{\beta^{-}}\cdot(\alpha_{u}+\alpha_{v}),\,\frac{\beta}{\beta^{-}}\cdot(\alpha_{u}+\alpha_{v})+\frac{1}{1+\varepsilon/4}\right[,$

implying that $w(u,v)$, which is an integer, cannot exist. The proof follows.

Recall that $u$ of $(u,v)\in M_{bad}$ is part of $V_{bad}$ only if
$\mathrm{\mathbf{w}\\!\deg}_{H}(u)-\beta\cdot\alpha_{u}>0$. Claim 1 then
implies that given $(u,v)\in M_{bad}$, if both $u$ and $v$ are in $V_{bad}$,
then
$\mathrm{\mathbf{w}\\!\deg}_{H_{bad}}(u)+\mathrm{\mathbf{w}\\!\deg}_{H_{bad}}(v)\geq\frac{\beta^{-}}{1+\varepsilon/4}$;
if only $u$ is in $V_{bad}$, then
$\mathrm{\mathbf{w}\\!\deg}_{H_{bad}}(u)\geq\frac{\beta^{-}}{1+\varepsilon/4}$.
We can thus infer that
$\frac{w(\tilde{E})}{|V_{bad}|}\geq\frac{\beta^{-}}{2\cdot(1+\varepsilon/4)}$
and we can rewrite (2) as
$\beta+W\geq\frac{\beta^{-}}{2W\cdot(1+\varepsilon/4)}+\frac{w(\tilde{E})}{\sum_{\tilde{u}\in\tilde{V}}\alpha_{u}},$
and therefore

$\left(\beta+W-\frac{\beta^{-}}{2W\cdot(1+\varepsilon/4)}\right)\cdot\sum_{\tilde{u}\in\tilde{V}}\alpha_{u}\geq
w(\tilde{E}).$ (4)

We now can rebound the expression of (1) as follows:

$\displaystyle\beta^{-}\cdot w(M_{G})$ $\displaystyle\leq\beta\cdot
w(M_{H})+\sum_{v\in
V_{bad}}(\mathrm{\mathbf{w}\\!\deg}_{H}(v)-\beta\cdot\alpha_{v})$
$\displaystyle\leq\beta\cdot w(M_{H})+\sum_{v\in
V_{bad}}\mathrm{\mathbf{w}\\!\deg}_{H_{bad}}(v)$ (using (2))
$\displaystyle\leq\beta\cdot w(M_{H})+w(\tilde{E})$
$\displaystyle\leq\left(2\beta+W-\frac{\beta^{-}}{2W\cdot(1+\varepsilon/4)}\right)\cdot
w(M_{H}).$ (using (4))

Re-arranging,

$\left(2\frac{\beta}{\beta^{-}}+\frac{W}{\beta^{-}}-\frac{1}{2W\cdot(1+\varepsilon/4)}\right)\cdot
w(M_{H})\geq w(M_{G}).$

As $\frac{\beta}{\beta^{-}}\leq 1+\varepsilon/4$ and
$\beta^{-}\geq\frac{4W}{\varepsilon}$ we obtain the desired result.

Then we can generalize this result to non-bipartite graphs.

######  Theorem 2.10.

Let $0<\varepsilon<1/2$ and $W$ be an integer parameter. Set
$\lambda=\frac{\varepsilon}{100W}$. For $\beta\geq\beta^{-}+2$ integers such
that $\frac{\beta}{\log(\beta)}\geq 2W^{2}\lambda^{-2}$ and
$\beta^{-}\geq(1-\lambda)\cdot\beta$, we have that any
$(\beta,\beta^{-})$-$w$-EDCS $H$ of a graph $G$ (with integer edge weights
bounded by $W$) contains a matching $M_{H}$ such that
$\left(2-\frac{1}{2W}+\varepsilon\right)\cdot w(M_{H})\geq w(M_{G})$.

Here we use the probabilistic method and Lovasz Local Lemma [8], as in [2].

######  Proposition 2.11 (Lovasz Local Lemma, see [8]).

Let $0<p<1$ and $d\geq 1$. Suppose $\mathcal{E}_{1},\dots,\mathcal{E}_{t}$ are
$t$ events such that $\mathbb{P}(\mathcal{E}_{i})\leq p$ for all
$i\in\\{1,2,\dots,t\\}$ and each $\mathcal{E}_{i}$ is mutually independent of
all but (at most) $d$ other events $\mathcal{E}_{j}$. If $(d+1)\cdot p<1/e$
then the event $\bigcap_{i=1}^{t}\overline{\mathcal{E}_{i}}$ occurs with non-
zero probability.

######  Proof 2.12 (Proof of Theorem 2.10).

Let $M_{G}$ be an optimal matching in $G$. Consider a randomly chosen
bipartite subgraph $\tilde{G}(L\cup R,\tilde{E})$ of $G$ such that:

  * •

for any edge $(u,v)\in M_{G}$, with probability $1/2$ we have $u\in L$ and
$v\in R$, and with probability $1/2$ the opposite;

  * •

for any vertex $v\in V$ unmatched by $M_{G}$, $v$ is assigned to $L$ or $R$
uniformly at random;

  * •

all these random choices are made independently;

  * •

the set of edges $\tilde{E}$ contains the edges of $G$ that have one endpoint
in $L$ and the other endpoint in $R$, _i.e._ $\tilde{E}=E\cap(L\times R)$.

Then we define $\tilde{H}=H\cap\tilde{G}$.

Take any vertex $v\in V$. Let us assume that $v$ is chosen in $L$ in
$\tilde{G}$ (the other case being symmetric). Then we have
$\mathrm{\mathbf{w}\\!\deg}_{\tilde{H}}(v)=\sum_{u\in
N_{H}(v)}\mathbbm{1}_{u\in R}\cdot w(u,v)$. Therefore,
$\mathbb{E}[\mathrm{\mathbf{w}\\!\deg}_{\tilde{H}}(v)]=\mathrm{\mathbf{w}\\!\deg}_{H}(v)/2$
($+w(v,v^{\prime})/2$ for some $v^{\prime}$ if $(v,v^{\prime})\in H$ is an
edge of $M_{G}$). Moreover, if $u$ and $u^{\prime}$ in $N_{H}(v)$ are matched
in $M_{G}$ then the random variables $\mathbbm{1}_{u\in R}\cdot w(v,u)$ and
$\mathbbm{1}_{u^{\prime}\in R}\cdot w(v,u^{\prime})$ and negatively
associated. Otherwise the other random variables $\mathbbm{1}_{u\in R}\cdot
w(v,u)$ are mutually independent. Thereby, using Hoeffding’s inequality (see
Appendix A.1), we get

$\displaystyle\mathbb{P}\left[\left|\mathrm{\mathbf{w}\\!\deg}_{\tilde{H}}(v)-\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(v)}{2}\right|\geq\lambda\cdot\beta+\frac{W}{2}\right]$
$\displaystyle\leq\mathbb{P}\left[\left|\mathrm{\mathbf{w}\\!\deg}_{\tilde{H}}(v)-\mathbb{E}[\mathrm{\mathbf{w}\\!\deg}_{\tilde{H}}(v)]\right|\geq\lambda\cdot\beta\right]$
$\displaystyle\leq
2\cdot\exp\left(-\frac{2\lambda^{2}\cdot\beta^{2}}{\deg_{H}(v)\cdot
W^{2}}\right)$ $\displaystyle\leq
2\cdot\exp\left(-\frac{2\lambda^{2}\cdot\beta^{2}}{\beta\cdot W^{2}}\right)$
$\displaystyle\leq
2\cdot\exp\left(-4\cdot\log\beta\right)=\frac{2}{\beta^{4}}$

where the first inequality comes from the inequality
$|\mathrm{\mathbf{w}\\!\deg}_{H}(v)/2-\mathbb{E}[\mathrm{\mathbf{w}\\!\deg}_{\tilde{H}}(v)]|\leq
W/2$, the third inequality comes from $\deg_{H}(v)\leq\beta$ (see Proposition
2.2), and the fourth one from $\beta\geq 2\cdot
W^{2}\cdot\lambda^{-2}\cdot\log\beta$.

Now define as $\mathcal{E}_{v}$ the event that
$\left|\mathrm{\mathbf{w}\\!\deg}_{\tilde{H}}(v)-\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(v)}{2}\right|\geq\lambda\cdot\beta+W/2$.
Note that $\mathcal{E}_{v}$ only depends on the choices for vertices in
$N_{H}(v)$ and therefore can only depend on at most $\beta^{2}$ other events
$\mathcal{E}_{u}$ for vertices $u$ which are neighbours to $N_{H}(v)$ in $H$
(as $\deg_{H}(u)\leq\beta$ for all $u\in V$, see Proposition 2.2). Hence we
can apply Lovasz Local Lemma (Proposition 2.11) to prove that the event
$\bigcap_{v\in V}\overline{\mathcal{E}_{v}}$ occurs with non-zero probability.
Then, conditioning on this event, we can show that $\tilde{H}$ is a
$(\tilde{\beta},\tilde{\beta}^{-})$-$w$-EDCS of $\tilde{G}$ for some
parameters $\tilde{\beta}$ and $\tilde{\beta}^{-}$.

First, to prove Property (i) of $w$-EDCS, let $(u,v)$ be any edge in
$\tilde{H}$. By events $\overline{\mathcal{E}_{u}}$ and
$\overline{\mathcal{E}_{v}}$ we have the inequality

$\displaystyle\mathrm{\mathbf{w}\\!\deg}_{\tilde{H}}(u)+\mathrm{\mathbf{w}\\!\deg}_{\tilde{H}}(v)$
$\displaystyle\leq\frac{1}{2}\cdot(\mathrm{\mathbf{w}\\!\deg}_{H}(u)+\mathrm{\mathbf{w}\\!\deg}_{H}(v))+2\lambda\beta+W$
$\displaystyle\leq\beta/2\cdot w(u,v)+2\lambda\beta+W$
$\displaystyle\leq\beta/2\cdot(1+4\lambda+2W/\beta)\cdot w(u,v).$

For Property (ii) of $w$-EDCS $\tilde{H}$, let $(u,v)$ be any edge in
$\tilde{G}\backslash\tilde{H}$. By events $\overline{\mathcal{E}_{u}}$ and
$\overline{\mathcal{E}_{v}}$ we have the inequality

$\displaystyle\mathrm{\mathbf{w}\\!\deg}_{\tilde{H}}(u)+\mathrm{\mathbf{w}\\!\deg}_{\tilde{H}}(v)$
$\displaystyle\geq\frac{1}{2}\cdot(\mathrm{\mathbf{w}\\!\deg}_{H}(u)+\mathrm{\mathbf{w}\\!\deg}_{H}(v))-2\lambda\beta-W$
$\displaystyle\geq\beta^{-}/2\cdot w(u,v)-2\lambda\beta-W$
$\displaystyle\geq\beta/2\cdot(1-5\lambda-2W/\beta)\cdot w(u,v),$

as $\beta^{-}\geq(1-\lambda)\cdot\beta$. Hence $\tilde{H}$ is a
$(\tilde{\beta},\tilde{\beta}^{-})$-$w$-EDCS of $\tilde{G}$ for
$\tilde{\beta}=\lceil\beta/2\cdot(1+4\lambda+2W/\beta)\rceil$ and
$\tilde{\beta}^{-}=\lfloor\beta/2\cdot(1-5\lambda-2W/\beta)\rfloor$.

The choices of $\lambda$, $\beta$, and $\beta^{-}$ guarantee that we can apply
Lemma 2.8 to the subgraph $\tilde{H}$ in $\tilde{G}$. In fact,

$\displaystyle\tilde{\beta}^{-}$
$\displaystyle\geq\beta/2\cdot(1-5\lambda-2W/\beta)-1$ $\displaystyle\geq
W^{2}\lambda^{-2}\cdot(1-5\lambda)-W-1$ as $\beta\geq 2W^{2}\lambda^{-2}$
$\displaystyle=\frac{100^{2}W^{4}}{\varepsilon^{2}}-\frac{500W^{3}}{\varepsilon}-W-1$
as $\lambda=\frac{\varepsilon}{100W}$
$\displaystyle\geq\frac{4W}{\varepsilon}$

and

$\displaystyle\frac{\tilde{\beta}}{\tilde{\beta}^{-}}$
$\displaystyle\leq\frac{\beta/2\cdot(1+4\lambda+2W/\beta)+1}{\beta/2\cdot(1-5\lambda-2W/\beta)-1}$
$\displaystyle=\frac{1+4\lambda+2W/\beta+2/\beta}{1-5\lambda-2W/\beta-2/\beta}$
$\displaystyle\leq\frac{1+4\lambda+\lambda^{2}/W+\lambda^{2}/W^{2}}{1-5\lambda-\lambda^{2}/W-\lambda^{2}/W^{2}}$
as $\beta\geq 2W^{2}\lambda^{-2}$
$\displaystyle\leq\frac{1+6\lambda}{1-7\lambda}$ as $\lambda\leq 1$ and $W\geq
1$ $\displaystyle\leq 1+20\lambda$ as $\lambda\leq\frac{1}{20}$ (standard
analysis) $\displaystyle=1+\frac{\varepsilon}{5W}$ as
$\lambda=\frac{\varepsilon}{100W}$

As $M_{\tilde{G}}=M_{G}$, $w(M_{\tilde{H}})\leq w(M_{H})$ (by construction),
and $\tilde{H}$ is a $(\tilde{\beta},\tilde{\beta}^{-})$-$w$-EDCS of
$\tilde{G}$, it follows from Lemma 2.8 that $H$ contains a matching $M_{H}$
such that $\left(2-\frac{1}{2W}+\varepsilon\right)\cdot w(M_{H})\geq
w(M_{G})$.

##  3 EDCS for Weighted $b$-Matchings

From now on we consider the problem of finding a maximum weight $b$-matching
in an edge-weighted multi-graph $G=(V,E)$. Hence we will use the notations
described in the introduction. Here we recall the generalization of edge-
degree constrained subgraphs (EDCS) to an edge-weighted multi-graph $G=(V,E)$
in the context of the $b$-matching problem.

######  Definition 3.1.

Let $G=(V,E)$ be a weighted multi-graph, $\\{b_{v}\\}_{v\in V}$ be a set of
constraints, and $H$ be a subgraph of $G$. Given any integer parameters
$\beta\geq 3$ and $\beta^{-}\leq\beta-2$, we say that $H$ is a
$(\beta,\beta^{-})$-$w$-$b$-EDCS of $G$ if $H$ satisfies the following
properties:

  1. (i)

For any edge $(u,v,w_{uv})\in H$,
$\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(u)}{b_{u}}+\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(v)}{b_{v}}\leq\beta\cdot
w_{uv}$

  2. (ii)

For any edge $(u,v,w_{uv})\in G\backslash H$,
$\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(u)}{b_{u}}+\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(v)}{b_{v}}\geq\beta^{-}\cdot
w_{uv}$.

As for a $w$-EDCS (Proposition 2.2), we can bound the degree of a vertex in a
$w$-$b$-EDCS $H$.

######  Proposition 3.2.

Let $H$ be a $(\beta,\beta^{-})$-$w$-$b$-EDCS of a given graph $G$. Then, for
all $v\in V$, we have $\deg_{H}(v)\leq\beta\cdot b_{v}$.

######  Proposition 3.3.

Let $H$ be a $(\beta,\beta^{-})$-$w$-$b$-EDCS of a given graph $G$. Then $H$
contains at most $2\beta\cdot|M_{G}|$ edges.

######  Proof 3.4.

A vertex $v\in V$ is called _saturated_ by $M_{G}$ if $|\delta_{G}(v)\cap
M_{G}|=b_{v}$. We denote by $V_{sat}$ the set of vertices saturated by
$M_{G}$. As $M_{G}$ is a maximal matching in $G$, it means that for all
$(u,v,w_{uv})\in G\backslash M_{G}$, either $u$ or $v$ is in $V_{sat}$. We
denote by $M_{sat}\subseteq M_{G}$ the subset of edges in $M_{G}$ that are
incident to a vertex of $V_{sat}$. By this definition, we get:

$\displaystyle|H|$ $\displaystyle=|H\cap(M_{G}\backslash
M_{sat})|+|H\backslash(M_{G}\backslash
M_{sat})|\leq|M_{G}|-|M_{sat}|+\sum_{v\in V_{sat}}\deg_{H}(v)$
$\displaystyle\leq|M_{G}|-|M_{sat}|+\sum_{v\in V_{sat}}\beta\cdot
b_{v}\leq|M_{G}|-|M_{sat}|+2\cdot|M_{sat}|\cdot\beta\leq 2\beta\cdot|M_{G}|$

as for all $v\in V$, $\deg_{H}(v)\leq\beta\cdot b_{v}$ and $\sum_{v\in
V_{sat}}b_{v}\leq 2\cdot|M_{sat}|$.

We can also show that such $w$-$b$-EDCSes always exist.

######  Proposition 3.5.

Any multi-graph $G=(V,E)$, along with a set of constraints $\\{b_{v}\\}_{v\in
V}$, contains a $(\beta,\beta^{-})$-$w$-$b$-EDCS for any parameters
$\beta\geq\beta^{-}+2$. Such a $(\beta,\beta^{-})$-$w$-$b$-EDCS can also be
found in $O(\beta^{2}W^{2}\cdot|M_{G}|)$ time.

######  Proof 3.6.

As in the proof of Proposition 2.4, we follow closely the argument of [2]. We
use the same local-search algorithm as the one in Proposition 2.4, except that
the properties violated are those of Definition 3.1. Here we also give the
priority to the correction of violations of Property (i), so that the at each
step of the algorithm all the vertices $v\in V$ have degrees bounded by
$\beta\cdot b_{v}+1$. To prove that this algorithm terminates and show the
existence of a $w$-$b$-EDCS, we introduce the following potential function:

$\Phi(H)=(2\beta-2)\sum_{(u,v,w_{uv})\in H}w_{uv}^{2}-\sum_{u\in
V}\frac{(\mathrm{\mathbf{w}\\!\deg}_{H}(u))^{2}}{b_{u}}.$

Observe that by the same argument used in Proposition 3.3 (where we only use
the fact that the degrees are bounded), the value of $\Phi(H)$ is bounded by
$2\beta W^{2}\cdot 2\beta|M_{G}|$. We can also show that after each local
improvement, the value of $\Phi(H)$ increases by at least $3/2$.

In fact, when Property (i) is not respected by some edge $(u,v,w_{uv})\in H$,
$\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(u)}{b_{u}}+\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(v)}{b_{v}}\geq\beta\cdot
w_{uv}+\frac{1}{b_{u}\cdot b_{v}}$. If we fix it by erasing this edge from $H$
the value of $\Phi(H)$ is increased by $-(2\beta-2)\cdot
w_{uv}^{2}+2\cdot\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(u)}{b_{u}}\cdot
w_{uv}+2\cdot\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(v)}{b_{v}}\cdot
w_{uv}-\frac{1}{b_{u}}\cdot w_{uv}^{2}-\frac{1}{b_{v}}\cdot
w_{uv}^{2}\geq-(2\beta-2)\cdot w_{uv}^{2}+2\cdot(\beta\cdot
w_{uv}+\frac{1}{b_{u}\cdot b_{v}})\cdot w_{uv}-\frac{1}{b_{u}}\cdot
w_{uv}^{2}-\frac{1}{b_{v}}\cdot
w_{uv}^{2}=(2-\frac{1}{b_{u}}-\frac{1}{b_{v}})\cdot
w_{uv}^{2}+\frac{2}{b_{u}\cdot b_{v}}\cdot w_{uv}\geq
2-\frac{1}{b_{u}}-\frac{1}{b_{v}}+\frac{2}{b_{u}\cdot b_{v}}\geq 3/2$
(studying the function $(x,y)\rightarrow 2+2\cdot xy-x-y$ on the domain
$[0,1]^{2}$).

When Property (ii) is not respected by some edge $(u,v,w_{uv})\in G\backslash
H$, it means that
$\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(u)}{b_{u}}+\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(v)}{b_{v}}\leq\beta^{-}\cdot
w_{uv}-\frac{1}{b_{u}\cdot b_{v}}$. If we insert $(u,v)$ in $H$, the value of
$\Phi(H)$ increases by $(2\beta-2)\cdot
w_{uv}^{2}-2\cdot\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(u)}{b_{u}}\cdot
w_{uv}-2\cdot\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(v)}{b_{v}}\cdot
w_{uv}-\frac{1}{b_{u}}\cdot w_{uv}^{2}-\frac{1}{b_{v}}\cdot
w_{uv}^{2}\geq(2\beta-2)\cdot w_{uv}^{2}-2\cdot(\beta^{-}\cdot
w_{uv}-\frac{1}{b_{u}\cdot b_{v}})\cdot w_{uv}-\frac{1}{b_{u}}\cdot
w_{uv}^{2}-\frac{1}{b_{v}}\cdot
w_{uv}^{2}\geq(2\cdot(\beta-\beta^{-})-2-\frac{1}{b_{u}}-\frac{1}{b_{v}})\cdot
w_{uv}^{2}+\frac{2}{b_{u}\cdot b_{v}}\cdot
w_{uv}\geq(2-\frac{1}{b_{u}}-\frac{1}{b_{v}})\cdot
w_{uv}^{2}+\frac{2}{b_{u}\cdot b_{v}}\cdot w_{uv}\geq 3/2$, as before and
because $\beta\geq\beta^{-}+2$.

Hence the algorithm terminates in $O(\beta^{2}W^{2}\cdot|M_{G}|)$ steps.

The main interest of these $w$-$b$-EDCSes is that they contain an (almost)
$2-\frac{1}{2W}$ approximation, as in the case of $w$-EDCSes in simple graphs
(Theorem 2.10).

See 1.4

######  Proof 3.7.

Consider a maximum weight $b$-matching $M_{G}$. We build from $H$ and $M_{G}$
new multi-graphs $H^{\prime}=(V^{\prime},E_{H}^{\prime})$ and
$G^{\prime}=(V^{\prime},E^{\prime})$ as follows. The set of vertices
$V^{\prime}$ contains, for each vertex $v\in V$, $b_{v}$ vertices
$v_{1},\dots,v_{b_{v}}$, so that $V^{\prime}$ contains $\sum_{v\in V}b_{v}$
vertices in total. To construct $E^{\prime}$, for each $v\in V$, we will
distribute the edges of $\delta(v)\cap(H\cup M_{G})$ among the $b_{v}$
vertices $v_{1},\dots,v_{b_{v}}$ in such a way so that the following three
properties hold:

  1. (i)

each $v_{i}$ has a most one edge of $M_{G}$ incident to it;

  2. (ii)

$G^{\prime}$ is a simple graph (_i.e._ with no multiple edges between two
given vertices);

  3. (iii)

each $v_{i}$ has a weighted degree in the interval
$\left[\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(v)}{b_{v}}-2W,\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(v)}{b_{v}}+3W\right]$.

The existence of such a distribution is guaranteed by Lemma A.2 (see Appendix
A.2). For the second property, it is crucial that the graph $G$ has at most
$\min(b_{u},b_{v})$ edges between any vertices $u$ and $v$. This property is
important in the proof of Theorem 2.10 (when negative association is used).
Then, for $H^{\prime}$, we just consider the restriction of $G^{\prime}$ to
the edges corresponding to $H$ (ignoring those from $M_{G}\backslash H$ in the
preceding construction).

Observe that $M_{G}$ corresponds a simple matching in $G^{\prime}$, and that
any simple matching in $H^{\prime}$ corresponds to a $b$-matching in $H$. Next
we show that $H^{\prime}$ is a $(\beta+6W,\beta^{-}-6W)$-$w$-EDCS in the
simple graph $G^{\prime}$. Consider an edge $(u_{i},v_{j})\in H^{\prime}$. It
corresponds to an edge $(u,v,w_{uv})$ of $H$ so
$\mathrm{\mathbf{w}\\!\deg}_{H^{\prime}}(u_{i})+\mathrm{\mathbf{w}\\!\deg}_{H^{\prime}}(v_{j})\leq\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(u)}{b_{u}}+\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(v)}{b_{v}}+6W\leq(\beta+6W)\cdot
w_{uv}$, so Property (i) of Definition 3.1 holds. Consider next an edge
$(u_{i},v_{j})\in G^{\prime}\backslash H^{\prime}$. It corresponds to an edge
$(u,v,w_{uv})$ of $M_{G}\backslash H$, so
$\mathrm{\mathbf{w}\\!\deg}_{H^{\prime}}(u_{i})+\mathrm{\mathbf{w}\\!\deg}_{H^{\prime}}(v_{j})\geq\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(u)}{b_{u}}+\frac{\deg_{H}(v)}{b_{v}}-6W\geq(\beta^{-}-6W)\cdot
w_{uv}$ (as there can be a difference of at most $b_{u}\cdot W$ between the
weighted degree of $u$ in $G^{\prime}$ and in $H^{\prime}$). Thus Property
(ii) of Definition 3.1 holds as well. To conclude, $H^{\prime}$ is a
$(\beta+6W,\beta^{-}-6W)$-$w$-EDCS of $G^{\prime}$, so by Theorem 2.10 we have
that $(2-\frac{1}{2W}+\varepsilon)\cdot w(M_{H^{\prime}})\geq
w(M_{G^{\prime}})=w(M_{G})$. As $w(M_{H})\geq w(M_{H^{\prime}})$ (because any
matching in $H^{\prime}$ corresponds to a $b$-matching of the same weight in
$H$), we complete the proof.

##  4 Application to $b$-Matchings in Random-Order Streams

In this section we consider the random-order stream model and we show how our
results in the preceding section can be adapted to get a
$2-\frac{1}{2W}+\varepsilon$ approximation.

As our algorithm builds on that of Bernstein [3] for the unweighted simple
matching, let us briefly summarize his approach. In the first phase of the
streaming, he constructs a subgraph that satisfies only a weaker definition of
EDCS in Definition 1.1 (only Property (i) holds). In the second phase of the
streaming, he collects the “underfull” edges, which are those edges that
violate Property (ii). He shows that in the end, the union of the subgraph
built in the first phrase and the underfull edges collected in the second
phase, with high probability, contains a $3/2+\varepsilon$ approximation and
that the total memory used is in the order of $O(n\cdot\log n)$. As we will
show below, this approach can be properly adapted to our context of edge-
weighted $b$-matching. Our main technical challenge lies in the fact that
unlike the simple matching, the size of $M_{G}$ can vary a lot. We need a
“guessing” strategy to ensure that the required memory is proportional to
$|M_{G}|$.

######  Definition 4.1.

We say that a graph $H$ has bounded weighted edge-degree $\beta$ if for every
edge $(u,v,w_{uv})\in H$,
$\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(u)}{b_{u}}+\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(v)}{b_{v}}\leq\beta\cdot
w_{uv}$.

######  Definition 4.2.

Let $G$ be any edge-weighted multi-graph, and let $H$ be a subgraph of $G$
with bounded weighted edge-degree $\beta$. For any parameter $\beta^{-}$, we
say that an edge $(u,v,w_{uv})\in G\backslash H$ is
$(H,\beta,\beta^{-})$-underfull if
$\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(u)}{b_{u}}+\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(v)}{b_{v}}<\beta^{-}\cdot
w_{uv}$.

######  Lemma 4.3.

Let $0<\varepsilon<1/2$ be any parameter and $W$ be an integer parameter. Set
$\lambda=\frac{\varepsilon}{100W}$. Suppose that $\beta^{-}$ and
$\beta\geq\beta^{-}+2$ are integers so that
$\frac{\beta+8W}{\log(\beta+8W)}\geq 2W^{2}\lambda^{-2}$ and
$\beta^{-}-6W\geq(1-\lambda)\cdot(\beta+8W)$, for any edge-weighted multi-
graph $G$ with integer weights in ${1,\dots,W}$, and for any subgraph $H$ with
bounded weighted edge-degree $\beta$, if $X$ contains all edges in
$G\backslash H$ that are $(H,\beta,\beta^{-})$-underfull, then
$(2-\frac{1}{2W}+\varepsilon)\cdot w(M_{H\cup X})\geq w(M_{G})$.

######  Proof 4.4.

First, observe that $H\cup X$ is not necessarily a $w$-$b$-EDCS of $G$.
Thereby we use another argument coming from [3]. Let $M_{G}$ be a maximum
weight $b$-matching in $G$, let $M_{G}^{H}=M_{G}\cap H$ and
$M_{G}^{G\backslash H}=M_{G}\cap(G\backslash H)$. Let $X^{M}=X\cap
M_{G}^{G\backslash H}$. We can observe that $w(M_{G})=w(M_{H\cup
M_{G}^{G\backslash H}})$. Then we can show that $H\cup X^{M}$ is a
$(\beta+2W,\beta^{-})$-$w$-$b$-EDCS of $H\cup M_{G}^{G\backslash H}$.

To show that $H\cup X^{M}$ is a $(\beta+2W,\beta^{-})$-$w$-$b$-EDCS of $H\cup
M_{G}^{G\backslash H}$, a first observation is that for all $v\in V$, we have
the inequalities
$\mathrm{\mathbf{w}\\!\deg}_{H}(v)\leq\mathrm{\mathbf{w}\\!\deg}_{H\cup
X^{M}}(v)\leq\mathrm{\mathbf{w}\\!\deg}_{H}(v)+b_{v}\cdot W$. We start with
Property (ii) of Definition 3.1. By construction, $X^{M}$ contains all edges
$(u,v,w_{uv})$ in $M_{G}^{G\backslash H}$, where the inequality
$\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(u)}{b_{u}}+\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(v)}{b_{v}}<\beta^{-}\cdot
w_{uv}$ is satisfied. Therefore, the remaining edges $(u,v,w_{uv})\in(H\cup
M_{G}^{G\backslash H})\backslash(H\cup X^{M})=M_{G}^{G\backslash H}\backslash
X^{M}$ satisfy the inequality
$\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(u)}{b_{u}}+\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(v)}{b_{v}}\geq\beta^{-}\cdot
w_{uv}$. For Property (i), for $(u,v,w_{uv})\in H$, we have
$\frac{\mathrm{\mathbf{w}\\!\deg}_{H\cup
X^{M}}(u)}{b_{u}}+\frac{\mathrm{\mathbf{w}\\!\deg}_{H\cup
X^{M}}(v)}{b_{v}}\leq(\beta+2W)\cdot w_{uv}$. And for $(u,v,w_{uv})\in X^{M}$,
$\frac{\mathrm{\mathbf{w}\\!\deg}_{H\cup
X^{M}}(u)}{b_{u}}+\frac{\mathrm{\mathbf{w}\\!\deg}_{H\cup
X^{M}}(v)}{b_{v}}<(\beta^{-}+2W)\cdot w_{uv}<(\beta+2W)\cdot w_{uv}$, so
Property (i) is also satisfied.

As a result, Theorem 1.4 can be applied in this case and we get that
$\left(2-\frac{1}{2W}+\varepsilon\right)\cdot w\left(M_{H\cup
X^{M}}\right)\geq w\left(M_{H\cup M_{G}^{G\backslash H}}\right)=w(M_{G})$,
thus concluding the proof.

######  Remark 4.5.

One can easily notice that there exist integers $\beta$ and $\beta^{-}$ that
are $O(poly(W,1/\varepsilon))$ satisfying the conditions of Lemma 4.3. From
now on, we will use the parameters $\lambda$, $\beta$, and $\beta^{-}$
satisfying the conditions of Lemma 4.3 and they are of values
$O(poly(W,1/\varepsilon))$.

Algorithm 1 Main algorithm computing a weighted $b$-matching for a random-
order stream

1:$H\leftarrow\emptyset$

2:$\forall\,0\leq
i\leq\log_{2}m,\,\alpha_{i}\leftarrow\left\lfloor\frac{\varepsilon\cdot
m}{\log_{2}(m)\cdot(2^{i+2}\beta^{2}W^{2}+1)}\right\rfloor$

3:for $i=0\dots\log_{2}m$ do

4: $\textsc{ProcessStopped}\leftarrow\textsc{False}$

5: for $2^{i+2}\beta^{2}W^{2}+1$ iterations do

6: $\textsc{FoundUnderfull}\leftarrow\textsc{False}$

7: for $\alpha_{i}$ iterations do

8: let $(u,v,w_{uv})$ be the next edge in the stream

9: if
$\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(u)}{b_{u}}+\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(v)}{b_{v}}<\beta^{-}\cdot
w_{uv}$ then

10: add edge $(u,v,w_{uv})$ to $H$

11: $\textsc{FoundUnderfull}\leftarrow\textsc{True}$

12: while there exists $(u^{\prime},v^{\prime},w_{u^{\prime}v^{\prime}})\in
H:\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(u^{\prime})}{b_{u^{\prime}}}+\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(v^{\prime})}{b_{v^{\prime}}}>\beta\cdot
w_{u^{\prime}v^{\prime}}$ do

13: remove $(u^{\prime},v^{\prime},w_{u^{\prime}v^{\prime}})$ from $H$

14: if $\textsc{FoundUnderfull}=\textsc{False}$ then

15: $\textsc{ProcessStopped}\leftarrow\textsc{True}$

16: break from the loop

17: if $\textsc{ProcessStopped}=\textsc{True}$ then

18: break from the loop

19:$X\leftarrow\emptyset$

20:for each $(u,v,w_{uv})$ remaining edge in the stream do

21: if
$\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(u)}{b_{u}}+\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(v)}{b_{v}}<\beta^{-}\cdot
w_{uv}$ then

22: add edge $(u,v,w_{uv})$ to $X$

23:return the maximum weight $b$-matching in $H\cup X$

The algorithm, formally described in Algorithm 1, can be separated into two
different phases of streaming. The first phase, corresponding to Lines 3-18,
constructs some a subgraph $H$ of bounded weighted edge-degree $\beta$ using
only a $\varepsilon$ fraction of the stream $E^{early}$. In the second phase,
the algorithm collects the underfull edges in the remaining part of the stream
$E^{late}$. As in [3] we use the idea that if no underfull edge was found in
an interval of size $\alpha$ (see Lines 6-13), it means that with high
probability the number of underfull edges remaining in the stream is bounded
by some value $\gamma=4\log(m)\frac{m}{\alpha}$. The issue is therefore to
choose the right size of interval $\alpha$, because we do not know the order
of magnitude of $|M_{G}|$ in the $b$-matching problem: if we do as in [3] by
choosing only one fixed size of intervals $\alpha$, then if $\alpha$ is too
small, the value of $\gamma$ will be too big compared to $|M_{G}|$, whereas if
the value of $\alpha$ is too large we will not be able to terminate the first
phase of the algorithm within the early fraction of size $\varepsilon m$.
Therefore, the idea in the first phase of the algorithm is to “guess” the
value of $\log_{2}|M_{G}|$ by trying successively larger and larger values of
$i$ (see Line 3). In fact, by setting $i_{0}=\lceil\log_{2}|M_{G}|\rceil$, we
know that the number of operations that can be performed on a $w$-$b$-EDCS is
bounded by $2^{i_{0}+2}\beta^{2}W^{2}$ (see the proof of Proposition 3.5). As
a result we know that the first phase should always stop at a time where $i$
is smaller or equal to $i_{0}$, and therefore at a time when
$\alpha_{i}\geq\alpha_{i_{0}}$. Then we can prove that with high probability
the number of remaining underfull edges in the stream is at most
$\gamma_{i}=4\log(m)\frac{m}{\alpha_{i}}$.

Algorithm 1 works when $M_{G}$ is neither too small nor too big. Here we will
first argue that the other border cases can be handled anyway. We first have
this easy lemma (its proof is very similar to that of Proposition 3.3).

######  Lemma 4.6.

We have the inequality $|G|\leq 2n\cdot|M_{G}|$.

######  Proof 4.7.

We denote by $V_{sat}$ the set of vertices saturated by $M_{G}$ and
$M_{sat}\subseteq M_{G}$ the subset of edges that are incident to a vertex of
$V_{sat}$. Recall that as $M_{G}$ is a maximal matching in $G$, for all
$(u,v,w_{uv})\in G\backslash M_{G}$, either $u$ or $v$ is in $V_{sat}$.
Therefore,

$\displaystyle|G|=|M_{G}\backslash M_{sat}|+|G\backslash(M_{G}\backslash
M_{sat})|$ $\displaystyle\leq|M_{G}|-|M_{sat}|+\sum_{v\in V_{sat}}\deg_{G}(v)$
$\displaystyle\leq|M_{G}|-|M_{sat}|+\sum_{v\in V_{sat}}n\cdot b_{v}$
$\displaystyle\leq|M_{G}|-|M_{sat}|+2\cdot|M_{sat}|\cdot n$ $\displaystyle\leq
2n\cdot|M_{G}|,$

as for all $v\in V$, $\deg_{G}(v)\leq n\cdot b_{v}$ and $\sum_{v\in
V_{sat}}b_{v}\leq 2\cdot|M_{sat}|$.

Then we use it to handle the case of small $b$-matchings.

######  Claim 2.

We can assume that $w(M_{G})\geq\frac{3W^{2}}{2\varepsilon^{2}}\log(m)$.

In fact, if $w(M_{G})<\frac{3W^{2}}{2\varepsilon^{2}}\log(m)$, then
$|M_{G}|<\frac{3W^{2}}{2\varepsilon^{2}}\log(m)$ and by Lemma 4.6 the graph
has only $m=O(n\cdot\frac{3W^{2}}{2\varepsilon^{2}}\cdot\log(m))$ edges, so
the whole graph can be stored so we can compute an exact solution only using
$O(n\cdot poly(\log(m),W,1/\varepsilon))$ memory.

######  Claim 3.

Assuming Claim 2, with probability at least $1-m^{-3}$ the late part of the
steam $E^{late}$ contains at least a $(1-2\varepsilon)$ fraction of the
optimal $b$-matching.

Consider a maximum weight $b$-matching $M_{G}=\\{f_{1},\ldots,f_{|M_{G}|}\\}$.
We define the random variables $X_{i}=\mathbbm{1}_{f_{i}\in E^{early}}\cdot
w(f_{i})$. Hence we have $\mathbb{E}[\sum X_{i}]=\varepsilon\cdot w(M_{G})$.
Moreover, the random variables $X_{i}$ are negatively associated, so we can
use Hoeffding’s inequality (see Appendix A.1) to get
$\mathbb{P}\left[\sum_{i=1}^{|M_{G}|}X_{i}\geq 2\varepsilon\cdot
w(M_{G})\right]\leq\exp\left(-\frac{2\cdot\varepsilon^{2}\cdot
w(M_{G})^{2}}{|M_{G}|\cdot
W^{2}}\right)\leq\exp\left(-\frac{2\cdot\varepsilon^{2}\cdot
w(M_{G})}{W^{2}}\right)\leq m^{-3}$, as we now assume that
$w(M_{G})\geq\frac{3W^{2}}{2\varepsilon^{2}}\log(m)$ (see Claim 2).

Recall that we defined $i_{0}=\lceil\log_{2}|M_{G}|\rceil$.

######  Claim 4.

We can assume that $\frac{\varepsilon\cdot
m}{\log_{2}(m)\cdot(2^{i_{0}+2}\beta^{2}W^{2}+1)}\geq 1$.

If this is not the case, then we can just store all the edges of $G$ as the
number of edges $m$ is bounded by
$\frac{\log_{2}(m)\cdot(2^{i_{0}+2}\beta^{2}W^{2}+1)}{\varepsilon}=O(|M_{G}|\cdot
poly(\log(m),W,1/\varepsilon))$ (as $\beta$ is $O(poly(W,1/\varepsilon))$, see
Remark 4.5). As a result, if at some point of the first phase we have not
stopped and we have $\alpha_{i}=0$, then we store all the remaining edges of
$E^{late}$ and we will be able to get a $(1-2\varepsilon)$ approximation with
high probability (because of Claim 3) using $O(|M_{G}|\cdot
poly(\log(m),W,1/\varepsilon))$ memory.

Then we can move to our main algorithm. The following lemma is very similar to
the one used in [3] (see the proof in the Appendix). It can then be combined
with previous lemmas and claims to prove that a $2-\frac{1}{2W}+\varepsilon$
approximation can be achieved with high probability.

######  Lemma 4.8.

The first phase of Algorithm 1 uses $O(\beta\cdot|M_{G}|)$ memory and
constructs a subgraph $H$ of $G$, satisfying the following properties:

  1. 1.

The first phase terminates within the first $\varepsilon m$ edges of the
stream.

  2. 2.

When the first phase terminates after processing some edge, we have:

    1. (a)

$H$ has bounded weighted edge degree $\beta$, and contains at most
$O(\beta\cdot|M_{G}|)$ edges.

    2. (b)

With probability at least $1-m^{-3}$, the total number of
$(H,\beta,\beta^{-})$-underfull edges in the remaining part of the stream is
at most $\gamma=O(|M_{G}|\cdot(\log(m))^{2}\cdot\beta^{2}W^{2}\cdot
1/\varepsilon)$.

######  Proof 4.9.

First, in each interval of size $\alpha_{i}$ processed until the first phase
terminates (except the last interval) there is at least one insertion/deletion
operation that is performed (as described in the proof of Proposition 3.5) and
therefore the total number of such processed intervals is bounded by
$4\beta^{2}W^{2}\cdot|M_{G}|+1$. As a result, the first phase ends with some
$i\leq i_{0}=\lceil\log_{2}|M_{G}|\rceil$, and the total number of edge
processed in the first phase is therefore bounded by $\varepsilon
m\cdot\frac{i_{0}}{\log_{2}(m)}\leq\varepsilon m$. For Property 2.a, as the
subgraph $H$ built always keeps a bounded weighed edge-degree $\beta$,
Proposition 3.3 implies that $H$ uses $O(\beta\cdot|M_{G}|)$ memory.

Now we turn to the last property. As mentioned previously, the intuition is
simple: the algorithm only exits the first phase if it fails to find a single
underfull edge in an entire interval (Line 14-16), and since the stream is
random, such an event implies that there are most likely few underfull edges
left in the stream.

To formalize this, we call the $j$-th time that Lines 7-13 are processed the
_epoch_ $j$. Let $\mathcal{A}_{j}$ be the event that FoundUnderfull is set to
False in epoch $j$. Let $\mathcal{B}_{j}$ be the event that the number of
$(H,\beta,\beta^{-})$-underfull edges in the remaining part of the stream is
larger than some $\gamma$. Note that the last property fails to hold if and
only if we have $\mathcal{A}_{j}\land\mathcal{B}_{j}$ for some $j$, so we want
to upper bound $\mathbb{P}[\mathcal{A}_{j}\land\mathcal{B}_{j}]$. Let
$E_{j}^{r}$ contains all edges in the graph that have not yet appeared in the
stream at the _beginning_ of epoch $j$ (r for remaining). Let $E^{e}_{j}$ be
the edges that appear in epoch $j$ (e for epoch), and note that $E^{e}_{j}$ is
a subset of size
$\alpha_{i}\geq\alpha_{i_{0}}=\alpha_{\lceil\log_{2}|M_{G}|\rceil}=\alpha$
chosen uniformly at random from $E^{r}_{j}$. Define $H_{j}$ to be the subgraph
$H$ at the beginning of epoch $j$, and define $E^{u}_{j}\subseteq E^{r}_{j}$
to be the set of remaing underfull edges with respect to $H_{j}$, $\beta$, and
$\beta^{-}$. Observe that because of event $\mathcal{A}_{j}$, the graph $H$
does not change throughout epoch $j$, so an edge that is underfull at any
point during the epoch will be underfull at the end as well. Thus,
$\mathcal{A}_{j}\land\mathcal{B}_{j}$ is equivalent to the event that
$|E^{u}_{j}|>\gamma$ but $E^{u}_{j}\cap E^{e}_{j}=\emptyset$.

Let $\mathcal{A}^{k}_{j}$ be the event that the $k$-th edge of epoch $j$ is
not in $E^{u}_{j}$. We have that
$\mathbb{P}[\mathcal{B}_{j}\land\mathcal{A}_{j}]\leq\mathbb{P}[\mathcal{A}_{j}\,|\,\mathcal{B}_{j}]\leq\mathbb{P}[\mathcal{A}^{1}_{j}\,|\,\mathcal{B}_{j}]\prod_{k=2}^{\alpha}\mathbb{P}[\mathcal{A}^{k}_{j}\,|\,\mathcal{B}_{j},\mathcal{A}^{1}_{j},\ldots,\mathcal{A}^{k-1}_{j}],$
the second inequality coming from the fact that $E^{e}_{j}$ is of size larger
or equal to $\alpha=\alpha_{\lceil\log_{2}|M_{G}|\rceil}$.

Now, observe that
$\mathbb{P}[\mathcal{A}^{1}_{j}\,|\,\mathcal{B}_{j}]<1-\frac{\gamma}{m}$
because the first edge of the epoch is chosen uniformly at random from the set
of $\leq m$ remaining edges, and the event fails if the chosen edge is in
$E^{u}_{j}$, where $|E^{u}_{j}|>\gamma$ by definition of $\mathcal{B}_{j}$.
Similarly, for any $k$,
$\mathbb{P}[\mathcal{A}^{k}_{j}\,|\,\mathcal{B}_{j},\mathcal{A}^{1}_{j},\ldots,\mathcal{A}^{k-1}_{j}]<1-\frac{\gamma}{m}$
because conditioning on the previous events $\mathcal{A}^{t}_{j}$ implies that
no edge from $E^{u}_{j}$ has yet appeared in this epoch, so there are still at
least $\gamma$ edges from $E^{u}_{j}$ left in the stream.

We now set $\gamma=4\log(m)\cdot\frac{m}{\alpha}=4\log(m)\cdot
m\cdot\left\lfloor\frac{\varepsilon\cdot
m}{\log_{2}(m)\cdot(2^{i_{0}+2}\beta^{2}W^{2}+1)}\right\rfloor^{-1}$, which is
$O(|M_{G}|\cdot(\log(m))^{2}\cdot\beta^{2}W^{2}\cdot 1/\varepsilon)$, as we
assumed that $\frac{\varepsilon\cdot
m}{\log_{2}(m)\cdot(2^{i_{0}+2}\beta^{2}W^{2}+1)}\geq 1$ (and there is at most
a factor $2$ between $\lfloor x\rfloor$ and $x$ if $x\geq 1$).

Combining the above equations yields that
$\mathbb{P}[\mathcal{B}_{j}\land\mathcal{A}_{j}]\leq(1-\frac{\gamma}{m})^{\alpha}=(1-\frac{4\log(m)}{\alpha})^{\alpha}\leq
m^{-4}$. There are clearly at most $m$ epochs, so union bounding over all of
them shows that the last property fails with probability at most $m^{-3}$, as
desired.

######  Theorem 4.10.

Let $\varepsilon>0$. Using Algorithm 1, with probability $1-2m^{-3}$, one can
extract from a randomly-ordered stream of edges a weighted $b$-matching with
an approximation ratio of $2-\frac{1}{2W}+\varepsilon$, using
$O(\max(|M_{G}|,n)\cdot poly(\log(m),W,1/\varepsilon))$ memory.

######  Proof 4.11.

Applying Lemma 4.3 to the graph $H\cup G^{late}$ we can get, choosing the
right values $\beta$ and $\beta^{-}$ (which are $O(poly(W,1/\varepsilon))$),
$H\cup X$ contains a $(1-2\varepsilon)^{-1}\cdot(2-\frac{1}{2W}+\varepsilon)$
approximation of the optimal $b$-matching (with probability at least
$1-m^{-3}$, see Claim 3), and with a memory consumption of $O(|M_{G}|\cdot
poly(\log(m),W,1/\varepsilon))$ (with probability at least $1-m^{-3}$, see
Lemma 4.8), with probability at least $1-2m^{-3}$ (union bound). Hence the
proof.

## References

  * [1] Sepehr Assadi and Soheil Behnezhad.  Beating two-thirds for random-order streaming matching.  In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference), volume 198 of LIPIcs, pages 19:1–19:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.  doi:10.4230/LIPIcs.ICALP.2021.19.
  * [2] Sepehr Assadi and Aaron Bernstein.  Towards a unified theory of sparsification for matching problems.  In Jeremy T. Fineman and Michael Mitzenmacher, editors, 2nd Symposium on Simplicity in Algorithms, SOSA 2019, January 8-9, 2019, San Diego, CA, USA, volume 69 of OASICS, pages 11:1–11:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.  doi:10.4230/OASIcs.SOSA.2019.11.
  * [3] Aaron Bernstein.  Improved Bounds for Matching in Random-Order Streams.  In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), volume 168 of Leibniz International Proceedings in Informatics (LIPIcs), pages 12:1–12:13, Dagstuhl, Germany, 2020. Schloss Dagstuhl–Leibniz-Zentrum für Informatik.  doi:10.4230/LIPIcs.ICALP.2020.12.
  * [4] Aaron Bernstein, Aditi Dudeja, and Zachary Langley.  A framework for dynamic matching in weighted graphs.  In Samir Khuller and Virginia Vassilevska Williams, editors, STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 668–681. ACM, 2021.  doi:10.1145/3406325.3451113.
  * [5] Aaron Bernstein and Cliff Stein.  Fully dynamic matching in bipartite graphs.  In Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, editors, Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, volume 9134 of Lecture Notes in Computer Science, pages 167–179. Springer, 2015.  doi:10.1007/978-3-662-47672-7\\_14.
  * [6] Aaron Bernstein and Cliff Stein.  Faster fully dynamic matchings with small approximation ratios.  In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 692–711. SIAM, 2016.  doi:10.1137/1.9781611974331.ch50.
  * [7] Jeno Egerváry.  Matrixok kombinatorius tulajdonságairól.  Matematikai és Fizikai Lapok, 38(1931):16–28, 1931.
  * [8] Paul Erdős and László Lovász.  Problems and results on 3-chromatic hypergraphs and some related questions.  In Colloquia Mathematica Societatis Janos Bolyai 10. Infinite and Finite Sets, Keszthely (Hungary). Citeseer, 1973.
  * [9] Alireza Farhadi, Mohammad Taghi Hajiaghayi, Tung Mai, Anup Rao, and Ryan A. Rossi.  Approximate maximum matching in random streams.  In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 1773–1785. SIAM, 2020.  doi:10.1137/1.9781611975994.108.
  * [10] Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang.  On graph problems in a semi-streaming model.  Theoretical Computer Science, 348:207–216, 12 2005.  doi:10.1016/j.tcs.2005.09.013.
  * [11] Buddhima Gamlath, Sagar Kale, Slobodan Mitrovic, and Ola Svensson.  Weighted matchings via unweighted augmentations.  In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC ’19, page 491–500, New York, NY, USA, 2019. Association for Computing Machinery.  doi:10.1145/3293611.3331603.
  * [12] Mohsen Ghaffari and David Wajc.  Simplified and Space-Optimal Semi-Streaming (2+$\varepsilon$)-Approximate Matching.  In Jeremy T. Fineman and Michael Mitzenmacher, editors, 2nd Symposium on Simplicity in Algorithms (SOSA 2019), volume 69 of OpenAccess Series in Informatics (OASIcs), pages 13:1–13:8, Dagstuhl, Germany, 2018. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.  doi:10.4230/OASIcs.SOSA.2019.13.
  * [13] Guru Prashanth Guruganesh and Sahil Singla.  Online matroid intersection: Beating half for random arrival.  In Friedrich Eisenbrand and Jochen Könemann, editors, Integer Programming and Combinatorial Optimization - 19th International Conference, IPCO 2017, Waterloo, ON, Canada, June 26-28, 2017, Proceedings, volume 10328 of Lecture Notes in Computer Science, pages 241–253. Springer, 2017.  doi:10.1007/978-3-319-59250-3\\_20.
  * [14] Chien-Chung Huang and François Sellier.  Maximum Weight b-Matchings in Random-Order Streams.  In Shiri Chechik, Gonzalo Navarro, Eva Rotenberg, and Grzegorz Herman, editors, 30th Annual European Symposium on Algorithms (ESA 2022), volume 244 of Leibniz International Proceedings in Informatics (LIPIcs), pages 68:1–68:14, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  URL: https://drops.dagstuhl.de/opus/volltexte/2022/17006, doi:10.4230/LIPIcs.ESA.2022.68.
  * [15] Chien-Chung Huang and François Sellier.  Semi-streaming algorithms for submodular function maximization under $b$-matching constraint.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021), 2021.
  * [16] Michael Kapralov.  Space lower bounds for approximating maximum matching in the edge arrival model.  In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 \- 13, 2021, pages 1874–1893. SIAM, 2021.  doi:10.1137/1.9781611976465.112.
  * [17] Christian Konrad.  A simple augmentation method for matchings with applications to streaming algorithms.  In Igor Potapov, Paul G. Spirakis, and James Worrell, editors, 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27-31, 2018, Liverpool, UK, volume 117 of LIPIcs, pages 74:1–74:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.  doi:10.4230/LIPIcs.MFCS.2018.74.
  * [18] Christian Konrad, Frédéric Magniez, and Claire Mathieu.  Maximum matching in semi-streaming with few passes.  In Anupam Gupta, Klaus Jansen, José D. P. Rolim, and Rocco A. Servedio, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Cambridge, MA, USA, August 15-17, 2012. Proceedings, volume 7408 of Lecture Notes in Computer Science, pages 231–242. Springer, 2012.  doi:10.1007/978-3-642-32512-0\\_20.
  * [19] Roie Levin and David Wajc.  Streaming submodular matching meets the primal-dual method.  In SODA, pages 1914–1933, 2021.
  * [20] Ami Paz and Gregory Schwartzman.  A $(2+\varepsilon)$-approximation for maximum weight matching in the semi-streaming model.  In Proceedings of the 2017 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2153–2161, 2017.  doi:10.1137/1.9781611974782.140.
  * [21] Moshe Tennenholtz.  Some tractable combinatorial auctions.  In AAAI/IAAI, pages 98–103, 2000.

##  Appendix A Details from Earlier Sections

###  A.1 Hoeffding’s Inequality

We recall the following probabilistic tool we will use in this paper.

######  Proposition A.1 (Hoeffding’s inequality).

Let $X_{1},\dots,X_{t}$ be $t$ negatively associated random variables that
take values in $[0,W]$. Let $X:=\sum_{i=1}^{t}X_{i}$. Then, for all
$\lambda>0$ we have:

$\mathbb{P}(X-\mathbb{E}[X]\geq\lambda)\leq\exp\left(-\frac{2\lambda^{2}}{t\cdot
W^{2}}\right)\,\text{ and }\,\mathbb{P}(|X-\mathbb{E}[X]|\geq\lambda)\leq
2\cdot\exp\left(-\frac{2\lambda^{2}}{t\cdot W^{2}}\right).$

###  A.2 Existence of the Edge Distribution for Theorem 1.4

######  Lemma A.2.

In the proof of Theorem 1.4, for $v\in V$, the edges of
$\delta_{G}(v)\cap(H\cup M_{G})$ can be distributed among the $b_{v}$ vertices
$v_{1},\dots,v_{b_{v}}$ so that:

  1. (i)

each $v_{i}$ has a most one edge of $M_{G}$ incident to it;

  2. (ii)

$G^{\prime}$ is a simple graph (_i.e._ with no multiple edge between two given
vertices);

  3. (iii)

each $v_{i}$ has a weighted degree in the interval
$\left[\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(v)}{b_{v}}-2W,\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(v)}{b_{v}}+3W\right]$.

######  Proof A.3.

Fix $v\in V$. Let us introduce some notation. We write
$S=\delta_{G}(v)\cap(H\cup M_{G})$. For all $u\in V$, $u\neq v$, we denote by
$S_{u}$ the multi-set of weighted edges between $u$ and $v$ in $H\cup M_{G}$,
_i.e._ $S_{u}=\delta_{G}(u)\cap\delta_{G}(v)\cap(H\cup M_{G})$. As
$|\delta_{G}(u)\cap\delta_{G}(v)|\leq\min(b_{u},b_{v})$, $|S_{u}|\leq b_{v}$.
Setting $s_{u}=|S_{u}|$, we denote by $S_{u}=\\{e_{u,1},\ldots,e_{u,s_{u}}\\}$
the multi-set of weighted edges between $u$ and $v$, assuming that
$w(e_{u,1})\geq\ldots\geq w(e_{u,s_{u}})$. Setting $m_{u}=|M_{G}\cap S_{u}|$,
we can assume that these $m_{u}$ edges from $M_{G}$ are
$e_{u,1},\ldots,e_{u,m_{u}}$ (as these are the heaviest edges in $S_{u}$).

Rephrasing, we want to distribute the edges of $S$ to $b_{v}$ sets
$E_{1},\ldots,E_{b_{v}}$, where each $E_{i}$ represents the set of adjacent
edges of vertex $v_{i}$ in $G^{\prime}$, in such a way that the following
holds:

  1. (i)

for all $1\leq i\leq b_{v}$, $|M_{G}\cap E_{i}|\leq 1$;

  2. (ii)

for all $1\leq i\leq b_{v}$, for all $u\in V$, $|S_{u}\cap E_{i}|\leq 1$;

  3. (iii)

the difference of the weights of these sets is upper-bounded by $2W$.

We present an algorithm (Algorithm 2) to obtain the desired distribution.
Roughly speaking, we consider all nodes $u\neq v$ one by one. For each $u$, we
use a greedy strategy to distribute the edges of $S_{u}$ into $s_{u}$ sets of
$E_{i}$s, where the sets $E_{i}$ are ordered according to increasing weights,
with the exception that the $E_{i}$s that have not received an edge in $M_{G}$
so far are the only ones able to receive an edge of $M_{G}$.

Algorithm 2 Algorithm to distribute the edges

1:$\forall\,1\leq i\leq b_{v},E_{i}\leftarrow\emptyset$

2:$\forall\,1\leq i\leq
b_{v},\textsc{UsedForMatching}_{i}\leftarrow\textsc{False}$

3:for $u\in V$ do

4: let $i_{1},\ldots,i_{m_{u}}$ be the indices of the $m_{u}$ sets $E_{i}$ not
UsedForMatching and having the smallest weights, ordered such that
$w(E_{i_{1}})\leq\ldots\leq w(E_{i_{m_{u}}})$

5: for $1\leq j\leq m_{u}$ do

6: add the edge $e_{u,j}$ to $E_{i_{j}}$

7: $\textsc{UsedForMatching}_{i_{j}}\leftarrow\textsc{True}$

8: let $i_{m_{u}+1},\ldots,i_{s_{u}}$ be the indices of the $s_{u}-m_{u}$ sets
$E_{i}$ having the smallest weights (excluding the indices
$i_{1},\ldots,i_{m_{u}}$), ordered such that $w(E_{i_{m_{u}+1}})\leq\ldots\leq
w(E_{i_{s_{u}}})$

9: for $m_{u}<j\leq s_{u}$ do

10: add the edge $e_{u,j}$ to $E_{i_{j}}$

By construction, it is clear that the two first properties are satisfied. We
prove the third property by establishing the following invariants:

  * •

Among two sets $E_{i}$ and $E_{j}$ both with UsedForMatching being false,
$|w(E_{j})-w(E_{i})|\leq W$.

  * •

Given a set $E_{i}$ with the variable UsedForMatching being false and another
set $E_{j}$ with the variable UsedForMatching being true,
$|w(E_{j})-w(E_{i})|\leq W$.

  * •

Among two sets $E_{i}$ and $E_{j}$ both with UsedForMatching being true,
$|w(E_{j})-w(E_{i})|\leq 2W$.

We can prove it by induction on the number of vertices $u\neq v$ processed so
far. To facilitate the proof, we can imagine that we add into $b_{v}-s_{u}$
edges of weight 0 into $S_{u}$ so that these edges are added into the sets
$E_{i_{s_{u}+1}},\cdots E_{i_{b_{v}}}$ immediately before the end of the loop.
In other words, all sets $E_{i}$ receive an edge each. Notice that by doing
this, we still ensure that the edges of $S_{u}$ are ordered in their non-
increasing weights while the sets $E_{i_{1}},\cdots,E_{i_{m_{u}}}$ and the
sets $E_{i_{m_{u}}+1},\cdots,E_{i_{b_{v}}}$ are ordered by non-decreasing
weights.

Consider two sets $E_{i}$ and $E_{j}$, then by induction hypothesis:

  * •

If $\textsc{UsedForMatching}_{i}=\textsc{UsedForMatching}_{j}=\textsc{False}$
before $u\in V$ is processed, then $|w(E_{i})-w(E_{j})|\leq W$. Suppose that
during this step, an edge $e_{i}$ is added to $E_{i}$ and an edge $e_{j}$ is
added to $E_{j}$. If $w(E_{i})=w(E_{j})$ then we are done, has the difference
cannot increase by more than $W$ (this happens if one set receives $W$ and the
other receives $0$). Now suppose for instance that $w(E_{i})>w(E_{j})$. Then,
as $E_{i}$ and $E_{j}$ have both not received edges from $M_{G}$ before $u$ is
processed, it means that we must have $w(e_{i})\leq w(e_{j})$, hence we also
get that $|w(E_{i}\cup\\{e_{i}\\})-w(E_{j}\cup\\{e_{j}\\})|\leq W$.

  * •

Similarly, if
$\textsc{UsedForMatching}_{i}=\textsc{UsedForMatching}_{j}=\textsc{True}$
before $u\in V$ is processed, then $|w(E_{i})-w(E_{j})|\leq 2W$. Suppose that
during this step, an edge $e_{i}$ is added to $E_{i}$ and an edge $e_{j}$ is
added to $E_{j}$. If $w(E_{i})=w(E_{j})$ then we are done, has the difference
cannot increase by more than $W$ (this happens if one set receives $W$ and the
other receives $0$). Now suppose for instance that $w(E_{i})>w(E_{j})$. Then,
as $E_{i}$ and $E_{j}$ have both received edges from $M_{G}$ before $u$ is
processed, it means that we must have $w(e_{i})\leq w(e_{j})$, hence we also
get that $|w(E_{i}\cup\\{e_{i}\\})-w(E_{j}\cup\\{e_{j}\\})|\leq 2W$.

  * •

Finally, if $\textsc{UsedForMatching}_{i}=\textsc{True}$ and
$\textsc{UsedForMatching}_{j}=\textsc{False}$ before $u$ is processed, then
$|w(E_{i})-w(E_{j})|\leq W$. If processing $u$ the variables UsedForMatching
have not changed, then it means that the edges for $E_{i}$ and $E_{j}$ have
been added during the phase of Lines 8-10 of the algorithm. As a result, the
argument for the previous cases also works here. Otherwise, it means that
$\textsc{UsedForMatching}_{j}$ is set to True as well during the process. As a
result the edge $e_{j}$ for $E_{j}$ has been added during the phase of Lines
4-7 while the edge $e_{i}$ for $E_{i}$ has been added during the phase of
Lines 8-10. The worst case happens when $w(E_{j})-w(E_{i})=W$, $w(e_{j})=W$,
and $w(e_{i})=0$, which leads to
$|w(E_{j}\cup\\{e_{j}\\})-w(E_{i}\cup\\{e_{i}\\})|=2W$.

To conclude, the maximum weight difference between two sets $E_{i}$ and
$E_{j}$ in the end is at most $2W$. Moreover, the total sum of the weights is
within the interval
$[\mathrm{\mathbf{w}\\!\deg}_{H}(v),\mathrm{\mathbf{w}\\!\deg}_{H}(v)+b_{v}\cdot
W]$ (because at most $b_{v}$ edges for $M_{G}$ have been added), therefore the
weights of all these sets are within the interval
$[\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(v)}{b_{v}}-2W,\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(v)}{b_{v}}+3W]$.

##  Appendix B Tightness of the Bound for Weighted EDCSes

######  Proposition B.1.

Let $W$ be an integer. Let $\beta\geq\beta^{-}+2$ be integer parameters.
Suppose that $\beta^{-}$ is divisible by $2W$. Then, there exists a graph $G$
and a $(\beta,\beta^{-})$-$w$-EDCS $H$ of $G$ such that the heaviest weighted
matching in $H$ is at best a $2+\frac{1}{\beta^{-}}-\frac{1}{2W}$
approximation of the largest weighted matching in $G$.

######  Proof B.2.

Consider the example depicted in Figure 1. Let $\beta^{-}=2kW$. The dashed
lines (not part of $H$) satisfy Property (ii) of Definition 2.1. We set $l$
such that $\beta=l+k+1$ so that the solid lines representing the edges
$(c_{i},b_{i})$ and $(d_{i},e_{i})$ satisfy Property (i) of Definition 2.1.
Here $l$ can be chosen to be large enough so that $\beta=\beta^{-}+2$.

By this construction, we have $w(M_{H})=2kW$ and

$\frac{w(M_{G})}{w(M_{H})}=\frac{2kW+l}{2kW}=1+\frac{\beta-k-1}{2kW}=1+\frac{\beta-1}{\beta^{-}}-\frac{1}{2W}\geq
2+\frac{1}{\beta^{-}}-\frac{1}{2W}.$

$a_{1}$$a_{2}$$\cdots$$a_{k}$$b_{1}$$b_{2}$$\cdots$$b_{k}$$c_{1}$$c_{2}$$\cdots$$c_{l}$$d_{1}$$d_{2}$$\cdots$$d_{l}$$e_{1}$$e_{2}$$\cdots$$e_{k}$$f_{1}$$f_{2}$$\cdots$$f_{k}$
Figure 1: The $w$-EDCS $H$ is represented by solid lines. All the solid edges
have weight $W$. The dashed edges are those that were not taken in the
$w$-EDCS $H$. All the dashed edges have weight $1$, so that we must have
$k\cdot W\geq\beta^{-}$. Edges in red are part of the optimal matching.

This gives an intuition on the approximation ratio $2-\frac{1}{2W}$ of Lemma
2.8 and hence Theorem 2.10, providing a tight example when $\beta^{-}$ is
divisible by $2W$. However, there is still a technical difficulty when
$\beta^{-}$ is not divisible by $2W$, coming from the fact that weigths have
to be integers.

##  Appendix C Using $W$ Copies Simple EDCSes does not Work

One could think that using $W$ copies of edge-degree constrained subgraphs,
one for each weight class, could lead to a structure containing a good
approximation of the optimal matching. Here we show that this idea does not
work. In fact, consider the simple example where the EDCS lead to a $3/2$
approximation, as depicted in Figure 2, where $\beta=2k+1$ and $\beta^{-}=2k$.
We represent this situation in a more compacted form, as in Figure 3.

$a_{1}$$a_{2}$$\cdots$$a_{k}$$b_{1}$$b_{2}$$\cdots$$b_{k}$$c_{1}$$c_{2}$$\cdots$$c_{k}$$d_{1}$$d_{2}$$\cdots$$d_{k}$$e_{1}$$e_{2}$$\cdots$$e_{k}$$f_{1}$$f_{2}$$\cdots$$f_{k}$
Figure 2: All edges are of the same weight. The EDCS $H$ is represented by
solid lines. The dashed edges are those that were not taken in the EDCS $H$.
Here $\frac{w(M_{G})}{w(M_{H})}=\frac{3}{2}$ $A$$B$$C$$D$$E$$F$ Figure 3: Each
set is of size $k$. The EDCS $H$ is represented by solid lines. The dashed
edges are those that were not taken in the EDCS $H$. Red lines represent
perfect matchings between sets whereas black lines represent complete
bipartite graphs between sets.

Using this compacted form, we can build a graph as in Figure 4. For each
weight class we have a situation where the approximation ratio $3/2$ is
reached, while all the matchings in the EDCS retained are intersecting. As a
result, the maximum weight maching in the union of EDCS is $2kW$ whereas the
actual maximum weight matching is of weight $2kW+\sum_{i=1}^{W}k\cdot
i=2kW+k\cdot\frac{W(W+1)}{2}$. Then the approximation ratio for $W\geq 3$ is
larger than $2$ and for $W=2$ the approximation ratio is
$\frac{7}{4}=2-\frac{1}{2\cdot 2}$ so for $W=2$ the approximation ratio is at
least the same as the one we can get with a $w$-EDCS.

$A_{1}$$\cdots$$A_{W}$$B$$C_{1}$$\cdots$$C_{W}$$D_{1}$$\cdots$$D_{W}$$E$$F_{1}$$\cdots$$F_{W}$
Figure 4: The edge-degree constrained subgraphs for each weight class are
represented by solid lines. The dashed edges are those that were not taken in
the EDCS. Red lines represent perfect matchings between sets while black lines
represent complete bipartite graphs between sets. The edges incident to
$A_{i}$, $C_{i}$, $D_{i}$, or $F_{i}$ are all of weight $i$.

##  Appendix D Streams Containing Irrelevant Edges

Here we no longer consider that the number of edges between two vertices $u$
and $v$ is bounded by $\min(b_{u},b_{v})$. We therefore introduce the notion
of _relevant edges_ in a multi-graph for a given set of constraints
$\\{b_{v}\\}_{v\in V}$.

######  Definition D.1.

In a multi-graph $G$, the multi-set of relevant edges between two given
vertices $u$ and $v$ is the multi-set of the $\min(b_{u},b_{v})$ edges in $G$
between $u$ and $v$ having the largest weights. The relevant subgraph
$\overline{G}$ of $G$ is the subgraph of $G$ made of these relevant edges.

Clearly, the only edges relevant to build a $b$-matching are these so-called
“relevant edges”, so we can always assume that $M_{G}=M_{\overline{G}}$.
Moreover, the notion of $w$-$b$-EDCS is relevant with respect to that relevant
subgraph.

We can then rephrase Theorem 1.4 using this of relevant subgraph:

######  Theorem D.2.

Let $0<\varepsilon<1/2$ and let $W$ be an integer parameter. Set
$\lambda=\frac{\varepsilon}{100W}$. Let $\beta\geq\beta^{-}+2$ be integers
such that $\frac{\beta+6W}{\log(\beta+6W)}\geq 2W^{2}\lambda^{-2}$ and
$\beta^{-}-6W\geq(1-\lambda)\cdot(\beta+6W)$. Then any
$(\beta,\beta^{-})$-$w$-$b$-EDCS $H$ of the relevant subgraph $\overline{G}$
of an edge-weighted multi-graph $G$ with integer edge weights bounded by $W$
contains a $b$-matching $M_{H}$ such that
$\left(2-\frac{1}{2W}+\varepsilon\right)\cdot w(M_{H})\geq w(M_{G})$.

We can also adapt the arguments of Section 4 to handle the more general case
of a stream containing relevant and irrelevant edges, introducing some small
variations in our previous argumentation.

######  Definition D.3.

We say that a graph $H$ has $b$-bounded weighted edge-degree $\beta$ if for
every edge $(u,v,w_{uv})\in H$,
$\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(u)}{b_{u}}+\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(v)}{b_{v}}\leq\beta\cdot
w_{uv}$ and $|\delta_{H}(u)\cap\delta_{H}(v)|\leq\min(b_{u},b_{v})$.

######  Definition D.4.

Let $G$ be any edge-weighted multi-graph, and let $H$ be a subgraph of $G$
with $b$-bounded weighted edge-degree $\beta$. For any parameter $\beta^{-}$,
we say that an edge $(u,v,w_{uv})\in G\backslash H$ is
$(H,\beta,\beta^{-})$-underfull if one of the following conditions is
satisfied:

  1. (i)

$|\delta_{H}(u)\cap\delta_{H}(v)|<\min(b_{u},b_{v})$ and
$\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(u)}{b_{u}}+\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(v)}{b_{v}}<\beta^{-}\cdot
w_{uv}$

  2. (ii)

$|\delta_{H}(u)\cap\delta_{H}(v)|=\min(b_{u},b_{v})$ and
$\min_{e^{\prime}\in\delta_{H}(u)\cap\delta_{H}(v)}w(e^{\prime})<w_{uv}$

We now show that one can always construct a large matching from the
combination of these two parts as well.

######  Lemma D.5.

Let $0<\varepsilon<1/2$ be any parameter and $W$ be an integer parameter. Set
$\lambda=\frac{\varepsilon}{100W}$. For $\beta\geq\beta^{-}+2$ integers such
that $\frac{\beta+8W}{\log(\beta+8W)}\geq 2W^{2}\lambda^{-2}$ and
$\beta^{-}-6W\geq(1-\lambda)\cdot(\beta+8W)$, for any edge-weighted multi-
graph $G$ with integer weights in ${1,\dots,W}$, and for any subgraph $H$ with
bounded weighted edge-degree $\beta$, if $X$ contains all edges in
$G\backslash H$ that are $(H,\beta,\beta^{-})$-underfull, then
$(2-\frac{1}{2W}+\varepsilon)\cdot w(M_{H\cup X})\geq w(M_{G})$.

######  Proof D.6.

Let $M_{G}$ be the maximum $b$-matching in $G$, let $M_{G}^{H}=M_{G}\cap H$
and $M_{G}^{G\backslash H}=M_{G}\cap(G\backslash H)$. Let $X^{M}=X\cap
M_{G}^{G\backslash H}$. We can observe that $w(M_{G})=w(M_{H\cup
M_{G}^{G\backslash H}})$.

Now we show that $\overline{H\cup X^{M}}$ is a
$(\beta+2W,\beta^{-})$-$w$-$b$-EDCS of $\overline{H\cup M_{G}^{G\backslash
H}}$. A first observation is that for all $v\in V$, we have the inequalities
$\mathrm{\mathbf{w}\\!\deg}_{H}(v)\leq\mathrm{\mathbf{w}\\!\deg}_{\overline{H\cup
X^{M}}}(v)\leq\mathrm{\mathbf{w}\\!\deg}_{H\cup
X^{M}}(v)\leq\mathrm{\mathbf{w}\\!\deg}_{H}(v)+b_{v}\cdot W$. We start with
Property (ii). By construction, $X^{M}$ contains all edges $(u,v,w_{uv})$ in
$M_{G}^{G\backslash H}$ such that
$\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(u)}{b_{u}}+\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(v)}{b_{v}}<\beta^{-}\cdot
w_{uv}$. Therefore, the remaining edges $(u,v,w_{uv})\in(H\cup
M_{G}^{G\backslash H})\backslash(H\cup X^{M})=M_{G}^{G\backslash H}\backslash
X^{M}$ satisfy the inequality
$\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(u)}{b_{u}}+\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(v)}{b_{v}}\geq\beta^{-}\cdot
w_{uv}$. For Property (i), for $(u,v,w_{uv})\in H$, we have
$\frac{\mathrm{\mathbf{w}\\!\deg}_{H\cup
X^{M}}(u)}{b_{u}}+\frac{\mathrm{\mathbf{w}\\!\deg}_{H\cup
X^{M}}(v)}{b_{v}}\leq(\beta+2W)\cdot w_{uv}$ (unless that edge is not relevant
in $H\cup M_{G}^{G\backslash H}$). And for $(u,v,w_{uv})\in X^{M}$,
$\frac{\mathrm{\mathbf{w}\\!\deg}_{H\cup
X^{M}}(u)}{b_{u}}+\frac{\mathrm{\mathbf{w}\\!\deg}_{H\cup
X^{M}}(v)}{b_{v}}<(\beta^{-}+2W)\cdot w_{uv}<(\beta+2W)\cdot w_{uv}$, so
Property (i) is also satisfied.

As a result, Theorem 1.4 can be applied in this case and we get that
$\left(2-\frac{1}{2W}+\varepsilon\right)\cdot w\left(M_{H\cup
X^{M}}\right)\geq w\left(M_{H\cup M_{G}^{G\backslash H}}\right)=w(M_{G})$,
thus concluding the proof.

Algorithm 3 Main algorithm computing a weighted $b$-matching for a random-
order stream

1:$H\leftarrow\emptyset$

2:$\forall\,0\leq
i\leq\log_{2}m,\,\alpha_{i}\leftarrow\left\lfloor\frac{\varepsilon\cdot
m}{\log_{2}(m)\cdot(2^{i+2}\beta^{2}W^{2}+1)}\right\rfloor$

3:for $i=0\dots\log_{2}m$ do

4: $\textsc{ProcessStopped}\leftarrow\textsc{False}$

5: for $2^{i+2}\beta^{2}W^{2}+1$ iterations do

6: $\textsc{FoundUnderfull}\leftarrow\textsc{False}$

7: for $\alpha_{i}$ iterations do

8: let $(u,v,w_{uv})$ be the next edge in the stream

9: if
$\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(u)}{b_{u}}+\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(v)}{b_{v}}<\beta^{-}\cdot
w_{uv}$ then

10: if $|\delta_{H}(u)\cap\delta_{H}(v)|=\min(b_{u},b_{v})$ then

11: if
$w_{uv}\leq\min_{e^{\prime}\in\delta_{H}(u)\cap\delta_{H}(v)}w(e^{\prime})$
then

12: continue $\triangleright$ irrelevant edge, we ignore it

13: remove the smallest edge linking $u$ and $v$

14: add edge $(u,v,w_{uv})$ to $H$

15: $\textsc{FoundUnderfull}\leftarrow\textsc{True}$

16: while there exists $(u^{\prime},v^{\prime},w_{u^{\prime}v^{\prime}})\in
H:\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(u^{\prime})}{b_{u^{\prime}}}+\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(v^{\prime})}{b_{v^{\prime}}}>\beta\cdot
w_{u^{\prime}v^{\prime}}$ do

17: remove $(u^{\prime},v^{\prime},w_{u^{\prime}v^{\prime}})$ from $H$

18: if $\textsc{FoundUnderfull}=\textsc{False}$ then

19: $\textsc{ProcessStopped}\leftarrow\textsc{True}$

20: break from the loop

21: if $\textsc{ProcessStopped}=\textsc{True}$ then

22: break from the loop

23:$X\leftarrow\emptyset$

24:for each $(u,v,w_{uv})$ remaining edge in the stream do

25: if
$\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(u)}{b_{u}}+\frac{\mathrm{\mathbf{w}\\!\deg}_{H}(v)}{b_{v}}<\beta^{-}\cdot
w_{uv}$ then

26: if $|\delta_{H}(u)\cap\delta_{H}(v)|=\min(b_{u},b_{v})$ and
$w_{uv}\leq\min_{e^{\prime}\in\delta_{H}(u)\cap\delta_{H}(v)}w(e^{\prime})$
then

27: continue $\triangleright$ irrelevant edge, we ignore it

28: add edge $(u,v,w_{uv})$ to $X$

29:return the maximum weight $b$-matching in $H\cup X$

The algorithm, formally described in Algorithm 3, is very similar to the one
in Section 4. However, when there are too many edges between two vertices $u$
and $v$, then another edge cannot be added, unless we remove another one
strictly smaller before that (see Lines 10-13). This “replacement” operation
increases at least by $1$ the value of the potential function used in the
construction of a $w$-$b$-EDCS and therefore this operation can be treated
like the insertion/deletion operations when bounding the number of such
operations. In the later phase of the stream, we also use the new defition of
underfull edges (see Lines 26-27).

As we will see later, Algorithm 3 works when $M_{G}$ is neither too small nor
too big, therefore we have show that these border cases can be handled anyway.

######  Lemma D.7.

Let $\overline{G}$ by the set of relevant edges in $G$. Then, we have
$|\overline{G}|\leq 2n\cdot|M_{G}|$.

######  Proof D.8.

Similar to the proof of Lemma 4.6.

######  Claim 5.

We can assume that $w(M_{G})\geq\frac{3W^{2}}{2\varepsilon^{2}}\log(m)$.

In fact, if $w(M_{G})<\frac{3W^{2}}{2\varepsilon^{2}}\log(m)$, then
$|M_{G}|<\frac{3W^{2}}{2\varepsilon^{2}}\log(m)$ and by Lemma 4.6 a semi-
streaming algorithm maintaining a _relevant_ graph (as defined in Lemma 4.6)
would only consume $O(n\cdot\frac{3W^{2}}{2\varepsilon^{2}}\cdot\log(m))$
memory. Therefore, such an auxiliary algorithm can be run in parallel of our
main algorithm and if the number of edge stored by that auxiliary algorithm
reaches $2n\cdot\frac{3W^{2}}{2\varepsilon^{2}}\cdot\log(m)$ then we stop that
auxiliary algorithm (as it means that
$|M_{G}|\geq\frac{3W^{2}}{2\varepsilon^{2}}\log(m)$). Otherwise, the whole
graph can be stored so we can compute an exact solution. In both cases we only
used $O(n\cdot poly(\log(m),W,1/\varepsilon))$ memory for that auxiliary
algorithm.

######  Claim 6.

Assuming Claim 5, with probability $1-m^{-3}$ the late part of the steam
$E^{late}$ contains at least a $(1-2\varepsilon)$ fraction of the optimal
$b$-matching.

Similar to the proof of Claim 3.

######  Claim 7.

We can assume that $\frac{\varepsilon\cdot
m}{\log_{2}(m)\cdot(2^{i_{0}+2}\beta^{2}W^{2}+1)}\geq 1$.

Similar to the proof of Claim 4.

Then we can move to our main algorithm.

######  Lemma D.9.

The first phase of Algorithm 1 uses $O(\beta\cdot|M_{G}|)$ memory and
constructs a subgraph $H$ of $G$, satisfying the following properties:

  1. 1.

The first phase terminates within the first $\varepsilon m$ edges of the
stream, _i.e._ processing an edge $e_{i}$ with $i\leq\varepsilon m$.

  2. 2.

When the first phase terminates after processing some edge $e_{i}$, the
subgraph $H\subseteq G$ constructed during this phase satisfies these
properties:

    1. (a)

$H$ has $b$-bounded weighted edge degree $\beta$, and hence contains at most
$O(\beta\cdot|M_{G}|)$ edges.

    2. (b)

With probability at least $1-m^{-3}$, the total number of
$(H,\beta,\beta^{-})$-underfull edges in the remaining part of the stream is
at most $\gamma=O(|M_{G}|\cdot(\log(m))^{2}\cdot\beta^{2}W^{2}\cdot
1/\varepsilon)$.

######  Proof D.10.

First, in each interval of size $\alpha_{i}$ processed until the first phase
terminates (except the last interval) there is at least one insertion/deletion
operation that is performed (as described in the proof of Proposition 3.5) or
a “replacement” operation (when an irrelevant edge is replaced by a larger
one, see Lines 10-13; note that this operation also increases the potential
function in the proof of Proposition 3.5 by at least $1$) and therefore the
total number of such processed intervals is bounded by
$4\beta^{2}W^{2}\cdot|M_{G}|+1$. As a result, the first phase ends for some
$i\leq i_{0}=\lceil\log_{2}|M_{G}|\rceil$, and the total number of edge
processed in the first phase is therefore bounded by $\varepsilon
m\cdot\frac{i_{0}}{\log_{2}(m)}\leq\varepsilon m$.

As the subgraph $H$ built always keeps a $b$-bounded weighted edge-degree
$\beta$, Proposition 3.3 also applies and therefore the construction of $H$
uses $O(\beta\cdot|M_{G}|)$ memory.

For the last property, the argument is very similar to the one used in the
proof of Lemma 4.8 and in [3].

Now we can obtain the desired result.

######  Theorem D.11.

Let $\varepsilon>0$ and $W$ be an integer parameter. Using Algorithm 3, with
probability $1-2m^{-3}$, one can extract from a randomly-ordered stream of
edges a weighted $b$-matching with an approximation ratio of
$2-\frac{1}{2W}+\varepsilon$, using $O(\max(|M_{G}|,n)\cdot
poly(\log(m),W,1/\varepsilon))$ memory.

######  Proof D.12.

Applying Lemma D.5 to the graph $H\cup G^{late}$ we can get, if we have chosen
the right values $\beta$ and $\beta^{-}$ (which are
$O(poly(W,1/\varepsilon))$), $H\cup X$ contains a
$(1-2\varepsilon)^{-1}\cdot(2-\frac{1}{2W}+\varepsilon)$ approximation of the
optimal $b$-matching (with probability at least $1-m^{-3}$, see Claim 6), and
with a memory consumption of $O(|M_{G}|\cdot poly(\log(m),W,1/\varepsilon))$
(with probability at least $1-m^{-3}$, see Lemma D.9), with probability at
least $1-2m^{-3}$ (by union bound). This concludes the proof.