Estimating Weighted Matchings in o(n) Space
Elena Grigorescu∗

Morteza Monemizadeh†

Samson Zhou‡

arXiv:1604.07467v3 [] 5 Sep 2016

September 6, 2016

Abstract
We consider the problem of estimating the weight of a maximum weighted matching of a weighted
graph G(V, E) whose edges are revealed in a streaming fashion. Extending the framework from Crouch
and Stubbs (APPROX 2014), we develop a reduction from the maximum weighted matching problem to
the maximum cardinality matching problem that only doubles the approximation factor of a streaming
algorithm developed for the maximum cardinality matching problem. Our results hold for the insertiononly and the dynamic (i.e, insertion and deletion) edge-arrival streaming models. The previous bestknown reduction is due to Bury and Schwiegelshohn (ESA 2015) who develop an algorithm whose
approximation guarantee scales by a polynomial factor.
As an application, we obtain improved estimators for weighted planar graphs and, more generally, for
weighted bounded-arboricity graphs, by feeding into our reduction the recent estimators due to Esfandiari
et al. (SODA 2015) and to Chitnis et al. (SODA 2016). In particular, we obtain a (48+ ǫ)-approximation
estimator for the weight of a maximum weighted matching in planar graphs.

1 Introduction
We study the problem of estimating the weight of a maximum weighted matching in a weighted graph
G(V, E) whose edges arrive in a streaming fashion. Computing a maximum cardinality matching (MCM)
in an unweighted graph and a maximum weighted matching (MWM) of a weighted graph are fundamental
problems in computational graph theory (e.g., [25], [13]).
Recently, the MCM and MWM problems have attracted a lot of attention in modern big data models
such as streaming (e.g., [12, 24, 23, 11, 1, 16, 2, 17, 3]), online (e.g., [5, 21, 6]), MapReduce (e.g., [22]) and
sublinear-time (e.g., [4, 27]) models.
Formally, the Maximum Weighted Matching problem is defined as follows.
Definition 1 (Maximum Weighted Matching (MWM)) Let G(V, E) be an undirected weighted graph with
edge weights w : E → R+ . A matching M in G is a set of pairwise non-adjacent edges; that is, no two
edges share a common
vertex. A matching M is called a maximum weighted matching of graph G if its
P
weight w(M) = edge e∈M w(e) is maximum.
∗

Department of Computer Science, Purdue University, West Lafayette, IN. Email: elena-g@purdue.edu.
Rutgers University, Piscataway, NJ 08854, USA. Supported by NSF CCF 1535878, IIS 1447793 and CCF 1161151. Email:
mortezam@dimacs.rutgers.edu.
‡
Department of Computer Science, Purdue University, West Lafayette, IN. Email: samsonzhou@gmail.com.
†

1

If the graph G is unweighted (i..e, w : E → {1} ), the maximum weighted matching problem becomes the
Maximum Cardinality Matching (MCM) problem.
In streaming models, the input graph is massive and the algorithm can only use a small amount of
working space to solve a computational task. In particular, the algorithm cannot store the entire graph
G = (V, E) in memory, but can only operate with a sublinear amount of space, preferably o(n), where
|V| = n. However, many tasks are not solvable in this amount of space, and in order to deal with such
problems, the semi-streaming model [12, 26] was proposed, which allows O(n polylog(n)) amount of
working space. Both these settings have been studied in the adversarial model, where the edge order may be
worst-case, and in the random order model, where the order of the edges is a uniformly random permutation
of the set of edges.
For matching problems, if the goal is to output a set of edges that approximates the optimum matching,
algorithms that maintain only Õ(n) edges cannot achieve better than (e/e − 1)-approximation ratio ([14],
[19]). Showing upper bounds has drawn a lot of recent interest (e.g., [12], [20], [23], [28], [10]), including a
recent result [15] showing a 3.5-approximation, which improves upon the previous 4-approximation of [9].
If, on the other hand, the goal is to output only an estimate of the size of the matching, and not a
matching itself, algorithms that use only o(n) space are both desirable and possible. Surprisingly, very little
is known about MWM/MCM in this model. Recent work by Kapralov et al. [18] shows the first polylog(n)
approximate estimator using only polylog(n) space for the MCM problem. Further, if Õ(n2/3 ) space is
allowed, then constant factor approximation algorithms are possible [11].
In a recent work, Bury and Schwiegelshohn [7] consider the MWM problem in o(n) space, showing a
reduction to the MCM problem, that scales the approximation factor polynomially. In particular, they are the
first to show a constant factor estimator for weighted graphs with bounded arboricity. Their results hold in
the adversarial insertion-only model (where the updates are only edge insertion), and in the dynamic models
(where the updates are both edge insertion and deletion). They also provide an Ω(n1−ǫ ) space lower bound
to estimate the matching within 1 + O(ǫ). Our results significantly improve the current best-known upper
bounds of [7], as detailed in the next section.

2 Our Contribution
We extend the framework of [9] to show a reduction from MWM to MCM that preserves the approximation
within a factor of 2(1 + ǫ). Specifically, given a λ-approximation estimation for the size of a maximum
cardinality matching, the reduction provides a (2(1 + ǫ) · λ)-approximation estimation of the weight of a
maximum weighted matching. Our algorithm works both in the insertion-only streaming model, and in the
dynamic setting. In both these models the edges appear in adversarial order.
We next state our main theorem. As it is typical for sublinear space algorithms, we assume that the
edge-weights of G = (V, E) are bounded by poly(n).
Theorem 2 Suppose there exists a streaming algorithm (in insertion-only, or dynamic
streaming model) that estimates the size of a maximum cardinality matching of an unweighted graph within a factor of λ, with probability at least (1−δ), using S(n, δ) space.
Then, for every ǫ > 0, there exists a streaming algorithm that estimates the weight of
a maximum weighted matching of a 
weighted
graph
 within
 a factor of 2λ(1 + ǫ), with

δ
probability at least (1 − δ), using O S n, c log n log n space.

2

We remark that if the estimator for MCM is specific to a monotone graph property (a property of graphs
that is closed under edge removal), then our algorithm can use it as a subroutine to obtain an estimator for
MWM in the weighted versions of the graphs with such properties (instead of using a subroutine for general
graphs, which may require more space, or provide worse approximation guarantees).
Our result improves the result of [7], who show a reduction from MWM to MCM that achieves a O(λ4 )approximation estimator for MWM, given a λ-approximation estimator for MCM. Their reduction also
allows extending MCM estimators to MWM estimators in monotone graph properties.
In particular, using specialized estimators for graphs of bounded arboricity, we obtain improved approximation guarantees compared with the previous best results of [7], as explained in Section 2.1, e.g., Table
2.1. In addition, our algorithm is natural and allows for a clean analysis.

2.1 Applications
Theorem 2 has immediate consequences for computing MWM in graphs with bounded arboricity. A graph
G = (V, E) has arboricity ν if


|E(U)|
,
ν = max
U⊆V |U| − 1
where E(U) is the subset of edges with both endpoints in U. The class of graphs with bounded arboricity
includes several important families of graphs, such as planar graphs, or more generally, graphs with bounded
degree, genus, or treewidth. Note that these families of graphs are monotone.
Graphs with Bounded Arboricity in the Insert-only Model Esfandiari et al. [11] provide an estimator
for the size of a maximum cardinality matching of an unweighted graph in the insertion-only streaming
model (for completeness we state their result as Theorem 5 in the Preliminaries). Theorem 2, together with
Theorem 5 (due to [11]) implies the following result.
Theorem 3 Let G be a weighted graph with arboricity ν and n = ω(ν2 ) vertices. Let ǫ, δ ∈ (0, 1).
Then, there exists an algorithm that estimates the weight of a MWM in G within a 2λ-approximation factor,
where λ = (5ν + 9)(1 + ǫ), in the insertion-only streaming model, with probability at least (1 − δ), using
Õ(νǫ−2 log(δ−1 )n2/3 )1 space. Both the update time and final processing time are O(log(δ−1 ) log n).
In particular, for planar graphs, ν = 3 and by choosing δ = n−1 in Theorem 3, and ǫ as a small constant,
the output of our algorithm is within (48 + ǫ)-approximation factor of a MWM, with probability at least
1 − n1 , using Õ(n2/3 ) space. The previous result of [7] gave an approximation factor of > 3 · 106 for planar
graphs.
Table 2.1 summarizes the state of the art for MWM.
Graphs with Bounded Arboricity in the Dynamic Model Our results also apply to the dynamic model.
Here we make use of the recent result of Chitnis et al. [8] that provides an estimator for MCM in the dynamic
model (See Theorem 6 in the Preliminaries).
Again, Theorem 6 satisfies the conditions of Theorem 2 with λ = (5ν + 9)(1 + ǫ), and consequently,
we have the following application.
1

Õ(f) = Õ(f · (log n)c ) for a large enough constant c.

3

[7]
Here

Approximation for Planar Graphs
> 3 · 106
48 + ǫ

Approximation for Graphs with Arboricity ν
12(5ν + 9)4
2(5ν + 9) + ǫ

Table 2.1: The insertion-only streaming model requires Õ(νǫ−2 log(δ−1 )n2/3 ) space for all graph classes,
while the dynamic streaming model requires Õ(νǫ−2 log(δ−1 )n4/5 ) space for all graph classes.
Theorem 4 Let G be a weighted graph with arboricity ν and n = ω(ν2 ) vertices. Let ǫ, δ ∈ (0, 1). Then,
there exists an algorithm that estimates the weight of a maximum weighted matching in G within a 2(5ν +
9)(1+ǫ)-factor in the dynamic streaming model with probability at least (1−δ), using Õ(νǫ−2 log(δ−1 )n4/5 )
space. Both the update time and final processing time are O(log(δ−1 ) log n).
In particular, for planar graphs, ν = 3, and by choosing δ = n−1 and ǫ as a small constant, the output of
our algorithm is a (48 + ǫ)-approximation of the weight of a maximum weighted matching with probability
at least 1 − n1 using at most Õ(n4/5 ) space.
We further remark that if 2-passes over the stream are allowed, then we may use the recent results of [8]
√
to obtain a (2(5ν + 9)(1 + ǫ))-approximation algorithm for MWM using only Õ( n) space.

2.2 Overview
We start by splitting the input stream into O(log n) substreams S1 , S2 , · · · , such that substream Si contains
every edge e ∈ E whose weight is at least (1 + ǫ)i , that is, w(e) ≥ (1 + ǫ)i . Splitting the stream into sets of
edges of weight only bounded below was used by Crouch and Stubbs in [9], leading to better approximation
algorithms for MWM in the semi-streaming model.
The construction from [9] explicitly saves maximal matchings in multiple substreams by employing
a greedy strategy for each substream. Once the stream completes, the algorithm from [9] again uses a
greedy strategy, by starting from the substream of highest weight and proceeding downward to streams of
lower weight. In each substream, the algorithm from [9] adds as many edges as possible, while retaining a
matching. However, with o(n) space, we cannot store maximal matchings in memory and so we no longer
have access to an oracle that explicitly returns edges from these matchings.
Instead, for each substream Si , we treat its edges as unweighted edges and apply a MCM estimator. We
then implicitly apply a greedy strategy, where we iteratively add as many edges possible from the remaining
substreams of highest weight, tracking an estimate for both the weight of a maximum weighted matching,
and the number of edges in the corresponding matching. The details of the algorithm appear in Section 4.
In our analysis, we use the simple but critical fact that, at any point, edges in our MWM estimator can
conflict with at most two edges in the MCM estimator, similar to an idea used in [9]. Therefore, if the MCM
estimator for a certain substream is greater than double the number of edges in the associated matching, we
add the remaining edges to our estimator, as shown below in Figure 2.2. Note that in some cases, we may
discard many edges that the algorithm of [9] chooses to output, but without being able to keep a maximal
matching, this may be unavoidable.
More formally, for each i, let U∗i be a maximum cardinality matching for Si . Then each edge of U∗i
intersects with either one, or two edges of U∗j , for all j < i. Thus, if |U∗i−1 | > 2|U∗i |, then at least |U∗i−1 | −
2|U∗i | edges from U∗i−1 can be added to U∗i while remaining a matching. We use a variable Bi to serve as an
estimator for this lower bound on the number of edges in a maximum weighted matching, including edges
from U∗j , for j ≥ i. We then use the estimator for MCM in each substream i as a proxy for U∗i .
4

U∗i−1

U∗i

U∗i−1

U∗i−1

Figure 2.2: If |U∗i | > 2|U∗i−1 |, then some edge(s) from U∗i−1 can be added while maintaining a matching.
Our algorithm differs from the algorithm of [7] in several points. They consider substreams Si containing
the edges with weight [2i , 2i+1 ), and their algorithm estimates the number of each edges in each stream, and
chooses to include the edges if both the number of the edges and their combined weight exceed certain
thresholds, deemed to contribute a significant value to the estimate. However, this approach may not capture
a small number of edges which nonetheless contribute a significant weight.
Our greedy approach is able to handle both these facets of a MWM problem. Namely, by greedily
taking as many edges as possible from the heavier substreams, and then accounting for edges that may be
conflicting with these in the next smaller substream, we are able to account for most of the weight. The
formal analysis appears in Section 5.

3 Preliminaries
Let S be a stream of insertions of edges of an underlying undirected weighted graph G(V, E) with weights
w : E → R. We assume that vertex set V is fixed and given, and the size of V is |V| = n. Observe that the

≤ n2 , so that we may assume that O(log |S|) = O(log n). Without
size of stream S is |S| ≤ n2 = n(n−1)
2
loss of generality we assume that at time i of stream S, edge ei arrives (or is revealed). Let Ei denote those
edges which are inserted (revealed)
up to time i, i.e., Ei = {e1 , e2 , e3 , · · · , ei }. Observe that at every time

i ∈ [|S|] we have |Ei | ≤ n2 ≤ n2 , where [x] = {1, 2, 3, · · · , x} for some natural number x. We assume that
at the end of stream S all edges of graph G(V, E) arrived, that is, E = E|S| .
We assume that there is a unique numbering for the vertices in V so that we can treat v ∈ V as a unique
number v for 1 ≤ v ≤ n = |V|. We
denote an undirected edge in E with two endpoints u, v ∈ V by (u, v).
n
The graph G can have at most 2 = n(n
 − 1)/2 edges. Thus, each edge can also be thought of as referring
to a unique number between 1 and n2 .
The next theorems imply our results for graphs with bounded arboricity in the insert-only and dynamic
models.
Theorem 5 [11] Let G be an unweighted graph with arboricity ν and n = ω(ν2 ) vertices. Let ǫ, δ ∈ (0, 1)
be two arbitrary positive values less than one. There exists an algorithm that estimates the size of a maximum
matching in G within a (5ν + 9)(1 + ǫ)-factor in the insertion-only streaming model with probability at
least (1 − δ), using Õ(νǫ−2 log(δ−1 )n2/3 ) space. Both the update time and final processing time are
O(log(δ−1 )). In particular, for planar graphs, we can (24+ǫ)-approximate the size of a maximum matching
with probability at least 1 − δ using Õ(n2/3 ) space.
5

Theorem 6 [8] Let G be an unweighted graph with arboricity ν and n = ω(ν2 ) vertices. Let ǫ, δ ∈
(0, 1) be two arbitrary positive values less than one. There exists an algorithm that estimates the size of a
maximum matching in G within a (5ν + 9)(1 + ǫ)-factor in the dynamic streaming model with probability
at least (1 − δ), using Õ(νǫ−2 log(δ−1 )n4/5 ) space. Both the update time and final processing time are
O(log(δ−1 )). In particular, for planar graphs, we can (24+ǫ)-approximate the size of a maximum matching
with probability at least 1 − δ using Õ(n4/5 ) space.

4 Algorithm
For a weighted graph G(V, E) with weights w : E → R such that the minimum weight of an edge is at least
c
1 and the maximum weight W of an edge is polynomially bounded in n, i.e.,
c,
 W = n for some constant
for T = ⌈log1+ǫ W⌉, we create T + 1 substreams such that substream Si = e ∈ S : w(e) ≥ (1 + ǫ)i .
Given access to a streaming algorithm MCM Estimator which estimates the size of a maximum cardinality matching of an unweighted graph G within a factor of λ with probability at least (1 − δ), we use
MCM Estimator as a black box algorithm on each Si and record the estimates. In general, for a substream
Si , we track an estimate Ai , of the weight of a maximum weighted matching of the subgraph whose edges
are in the substream Si , along with an estimate, Bi , which represents the number of edges in our estimate
Ai . The estimator Bi also serves as a running lower bound estimator for the number of edges in a maximum
matching. We greedily add edges to our estimation of the weight of a maximum weighted matching of graph
[
G. Therefore, if the estimator M
i−1 for the maximum cardinality matching of the substream Si−1 is more
than double the number of edges in Bi represented by our estimate Ai of the substream Si , we let Bi−1 be
i−1 . We iterate through
[
[
Bi plus the difference M
i−1 − 2Bi , and let Ai−1 be Ai plus (Mi−1 − 2Bi ) · (1 + ǫ)
the substream estimators, starting from the substream ST of largest weight, and proceeding downward to
dT , equivalent to taking all
substreams of lower weight. We initialize our greedy approach by setting BT = M
d
edges in MT .

Algorithm 1 Estimating Weighted Matching in Data Streams
Input: A stream S of edges of an underlying graph G(V, E) with weights w : E → R+ such that the
maximum weight W of an edge is polynomially bounded in n, i.e, W = nc for some constant c.
^ of w(M∗ ), the weight of a maximum weighted matching M∗ , in G.
Output: An estimator A
1: Let Ai be a running estimate for the weight of a maximum weighted matching.
2: Let Bi be a running lower bound estimate for the number of edges in a maximum weighted matching.
\
3: Initialize AT +1 = 0, BT +1 = 0, and M
T +1 = 0.
4: for i = T to i = 0 do
5:
Let Si = {e ∈ S : w(e) ≥ (1 + ǫ)i } be a substream of S of edges whose weights are at least (1 + ǫ)i .
6:
Let Si′ be unweighted versions of edges in Si .
7:
Let Sbi′ be the output of MCM Estimator for each Si′ with parameter δ ′ = Tδ .
b′
ci = max(M
[
8:
Let M
i+1 , Si ).
ci − 2Bi+1 ⌉).
9:
Set ∆i = max(0, ⌈M
10:
Update Bi = Bi+1 + ∆i .
11:
Update Ai = Ai+1 + (1 + ǫ)i ∆i .
^ = A0 .
12: Output estimate A
We note that the quantities Ai and Bi satisfy the following properties, which will be useful in the analysis.
6

Observation 7 Aj =

PT

Observation 8 Bj =

PT

+ ǫ)i ∆i

i=j (1

i=j ∆i

5 Analysis
ci ≤ 2Bi .
Lemma 9 For all i, Bi ≤ M

Proof : We prove the statement by induction on i, starting from i = T down to i = 0. For the base case
ci , so Bi = Bi+1 + ∆i = M
ci , and the desired inequality
i = T , we initialize Bi+1 = 0. In particular, ∆i = M
follows.
c
[
Now, we suppose the claim is true for Bi+1 ≤ M
i+1 ≤ 2Bi+1 . Next, we prove it for Bi ≤ Mi ≤ 2Bi . To
c
prove the claim for i we consider two cases. The first case is when 2Bi+1 < Mi . Then
Bi = Bi+1 + ∆i
ci − 2Bi+1
= Bi+1 + M

Additionally,

(By definition)
ci − 2Bi+1 )
(∆i = M

ci − Bi+1
=M
ci
≤M

ci < M
ci + (M
ci − 2Bi+1 )
M
ci − 2Bi+1 ))
= 2(Bi+1 + (M

ci )
(2Bi+1 < M
ci − 2Bi+1 )
(∆i = M

= 2(Bi+1 + ∆i )
= 2Bi

(By definition)

ci ≤ 2Bi .
and so Bi ≤ M

ci ≤ 2Bi+1 . Then, by definition, Bi = Bi+1 . Since S ′ is a subset of S ′ , then
The second case is when M
i+1
i
[
Bi = Bi+1 ≤ M
i+1

(Inductive hypothesis)
b′
ci = max(M
[
(M
i+1 , S ))

ci
≤M

i

≤ 2Bi+1 = 2Bi
ci ≤ 2Bi , which completes the proof.
and again Bi ≤ M

ci ≤ 2Bi+1 )
(M

✷

ci satisfies M
ci ≤ |U∗ | ≤ λM
ci , where U∗ is the size of a
Corollary 10 Suppose for all i, the estimator M
i
i
′
∗
maximum cardinality matching of Si . Then Bi ≤ |Ui | ≤ 2λBi .
ci ≤ 2Bi , so then λM
ci ≤ 2λBi . Similarly, by Lemma 9, Bi ≤ M
ci . But by
Proof : By Lemma 9, M
∗
ci ≤ |U | ≤ λM
ci , and so
assumption, M
i
ci ≤ |U∗ | ≤ λM
ci ≤ 2λBi .
Bi ≤ M
i
7

✷

ci satisfies M
ci ≤ |U∗ | ≤ λM
ci , where U∗ is the size of a
Lemma 11 Suppose for all i, the estimator M
i
i
maximum cardinality matching of Si′ . Then for all j,
T
X
i=j

∆i ≤

T
X
i=j

∗

|M ∩ (Sj − Sj+1 )| ≤

T
X

2λ∆i ,

i=j

where M∗ is a maximum weighted matching.
Proof : Since M∗ is a matching, then the number of edges in M∗ with weight at least (1 + ǫ)j is at most
|U∗j |. Thus,
T
X
|M∗ ∩ (Sj − Sj+1 )| ≤ |U∗j |.
i=j

Note that by Observation 8,

PT

i=j ∆i

= Bj , so then by Corollary 10,

T
X
i=j

|M∗ ∩ (Sj − Sj+1 )| ≤ 2λ

T
X

∆i .

i=j

On the other hand, Bi is a running estimate of the lower bound on the number of edges in M∗ ∩ Si , so
T
X
i=j

∆i = B j ≤

T
X
i=j

|M∗ ∩ (Sj − Sj+1 )|,

as desired.

✷

ci satisfies M
ci ≤ |U∗ | ≤ λM
ci for all i, where
Lemma 12 With probability at least 1 − δ, the estimator M
i
∗
′
Ui is the maximum cardinality matching of Si .
ci ≤ |U∗ | ≤ λM
ci succeeds with probability at least 1− δ , then the probability M
^ i succeeds
Proof : Since M
i
T
for i = 1, 2, . . . , T is at least 1 − δ by a union bound.
✷
We now prove our main theorem.
Proof of Theorem 2: We complete the proof of Theorem 2 by considering the edges in a maximum
weighted matching M∗ . We partition these edges by weight and bound the number of edges in each partition.
We will show that A0 ≤ w(M∗ ) ≤ 2λ(1 + ǫ)A0 . First, we have
X
w(M∗ ) =
w(e)
e∈M∗

=

T
X

X

w(e)

(2)

(1 + ǫ)i+1

(3)

i=0 e∈M∗ ∩(Si −Si+1 )

≤

T
X
i=0

X
e∈M∗ ∩(S

i −Si+1 )

8

≤
≤

T
X
i=0
T
X

|M∗ ∩ (Si − Si+1 )|(1 + ǫ)i+1

(4)

2λ∆i (1 + ǫ)i+1

(5)

T
X

(6)

i=0

≤ 2λ(1 + ǫ)

∆i (1 + ǫ)i = 2λ(1 + ǫ)A0 ,

i=0

where the identity in line (2) results from partitioning the edges by weight, so that e ∈ M∗ appears in
Si − Si+1 if (1 + ǫ)i ≤ w(e) < (1 + ǫ)i+1 . The inequality in line (3) results from each edge e in Si − Si+1
having weight less than (1+ǫ)i+1 , so an upper bound on the sum of the weights of edges in M∗ ∩(Si −Si+1 )
is (1 + ǫ)i+1 times the number of edges in |M∗ ∩ (Si − Si+1 )|, as shown in line (4). By Lemma 11, the
partial sums of 2λ∆i dominates the partial sums of |M∗ ∩ (Si − Si+1 |, resulting in the inequality in line (5).
The final identity in line (6) results from Observation 7. Similarly,
X
w(e)
w(M∗ ) =
e∈M∗

=

T
X

X

w(e)

(2)

(1 + ǫ)i

(3)

i=0 e∈M∗ ∩(Si −Si+1 )

≥
≥
≥
≥

T
X

X

i=0 e∈M∗ ∩(Si −Si+1 )
T
X

|M∗ ∩ (Si − Si+1 )|(1 + ǫ)i

(4)

T
X

∆i (1 + ǫ)i

(5)

i=0
T
X

Ai = A0 ,

(6)

i=0

i=0

where the identity in line (2) again results from partitioning the edges by weight, so that e ∈ M∗ appears in
Si − Si+1 if (1 + ǫ)i ≤ w(e) < (1 + ǫ)i+1 . The inequality in line (3) results from each edge e in Si − Si+1
having weight at least (1 + ǫ)i , so a lower bound on the sum of the weights of edges in M∗ ∩ (Si − Si+1 ) is
(1 + ǫ)i times the number of edges in |M∗ ∩ (Si − Si+1 )|, as shown in line (4). By Lemma 11, the partial
sums of |M∗ ∩ (Si − Si+1 )| dominates the partial sums of ∆i , resulting in the inequality in line (5). The final
identity in line (6) results from Observation 7.
b = A0 is a 2λ(1 + ǫ)-approximation for w(M∗ ).
Thus, A

Note that the assumption of Lemma 11 holds with probability at least 1 − δ by Lemma 12. Since we require
ci ≤ |U∗ | ≤ λM
ci with probability at least 1 − δ , then S n, δ space is required for each estimator.
M
i
T
T
9

c
Since
 W substreams are used and W ≤ n for some constant c, then the overall space necessary is
 T = log
δ
✷
S n, c log
n (c log n). This completes the proof.

Acknowledgements
We would like to thank anonymous reviewers for their helpful comments regarding the presentation of the
paper.

References
[1] Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Analyzing graph structure via linear measurements. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms,
SODA, pages 459–467, 2012.
[2] Abhash Anand, Surender Baswana, Manoj Gupta, and Sandeep Sen. Maintaining approximate maximum weighted matching in fully dynamic graphs. In IARCS Annual Conference on Foundations of
Software Technology and Theoretical Computer Science, FSTTCS, pages 257–266, 2012.
[3] Sepehr Assadi, Sanjeev Khanna, Yang Li, and Grigory Yaroslavtsev. Maximum matchings in dynamic
graph streams and the simultaneous communication model. In Proceedings of the Twenty-Seventh
Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1345–1364, 2016.
[4] S. Baswana, M. Gupta, and S. Sen. Fully dynamic maximal matching in O(log n) update time. In
Proceedings of the 52nd IEEE Symposium on Foundations of Computer Science (FOCS), pages 383–
392, 2011.
[5] Benjamin E. Birnbaum and Claire Mathieu. On-line bipartite matching made simple. SIGACT News,
39(1):80–87, 2008.
[6] Bartlomiej Bosek, Dariusz Leniowski, Piotr Sankowski, and Anna Zych. Shortest augmenting paths
for online matchings on trees. In Approximation and Online Algorithms - 13th International Workshop,
WAOA. Revised Selected Papers, pages 59–71, 2015.
[7] Marc Bury and Chris Schwiegelshohn. Sublinear estimation of weighted matchings in dynamic data
streams. In Algorithms - ESA - 23rd Annual European Symposium, Proceedings, pages 263–274, 2015.
[8] Rajesh Chitnis, Graham Cormode, Hossein Esfandiari, MohammadTaghi Hajiaghayi, Andrew McGregor, Morteza Monemizadeh, and Sofya Vorotnikova. Kernelization via sampling with applications
to finding matchings and related problems in dynamic graph streams. In Proceedings of the TwentySeventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1326–1344, 2016.
[9] M. Crouch and D. S. Stubbs. Improved streaming algorithms for weighted matching, via unweighted
matching. In Proceedings of the 17th International Workshop on Randomization and Approximation
Techniques in Computer Science (RANDOM), pages 96–104, 2014.
[10] L. Epstein, A. Levin, J. Mestre, and D. Segev. Improved approximation guarantees for weighted
matching in the semi-streaming model. SIAM J. Discrete Math, 25(3):1251–1265, 2011.
10

[11] H. Esfandiari, M. T. Hajiaghayi, V. Liaghat, M. Monemizadeh, and K. Onak. Streaming algorithms
for estimating the matching size in planar graphs and beyond. In SODA, pages 1217–1233, 2015.
[12] J. Feigenbaum, S. Kannan, McGregor, S. Suri, and J. Zhang. On graph problems in a semi-streaming
model. Theoretical Computer Science, 348(2-3):207–216, 2005.
[13] H. N. Gabow. Data structures for weighted matching and nearest common ancestors with linking. In
Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 434–
443, 1990.
[14] Ashish Goel, Michael Kapralov, and Sanjeev Khanna. On the communication and streaming complexity of maximum bipartite matching. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 468–485, 2012.
[15] Elena Grigorescu, Morteza Monemizadeh, and Samson Zhou. Streaming weighted matchings: Optimal meets greedy. CoRR, abs/1608.01487, 2016.
[16] S. Guha and A. McGregor. Graph synopses, sketches, and streams: A survey. PVLDB, 5(12):2030–
2031, 2012.
[17] Manoj Gupta and Richard Peng. Fully dynamic (1+ e)-approximate matchings. In 54th Annual IEEE
Symposium on Foundations of Computer Science, FOCS, pages 548–557, 2013.
[18] M. Kapralov, S. Khanna, and M. Sudan. Approximating matching size from random streams. In
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages
734–751, 2014.
[19] Michael Kapralov. Better bounds for matchings in the streaming model. In Proceedings of the TwentyFourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1679–1697, 2013.
[20] C. Konrad, F. Magniez, and C. Mathieu. Maximum matching in semi-streaming with few passes.
In Proceedings of the 15th IInternational Workshop on Approximation Algorithms for Combinatorial
Optimization Problems (APPROX), pages 231–242, 2012.
[21] Nitish Korula, Vahab S. Mirrokni, and Morteza Zadimoghaddam. Bicriteria online matching: Maximizing weight and cardinality. In Web and Internet Economics - 9th International Conference, WINE,
Proceedings, pages 305–318, 2013.
[22] Silvio Lattanzi, Benjamin Moseley, Siddharth Suri, and Sergei Vassilvitskii. Filtering: a method for
solving graph problems in mapreduce. In SPAA: Proceedings of the 23rd Annual ACM Symposium on
Parallelism in Algorithms and Architectures, pages 85–94, 2011.
[23] A. McGregor. Finding graph matchings in data streams. In Proceedings of the of 8th IInternational
Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages
170–181, 2005.
[24] Andrew McGregor. Graph mining on streams. In Encyclopedia of Database Systems, pages 1271–
1275. Springer, 2009.

11

p
[25] S. Micali and V. V. Vazirani. An o( |V||e|) algorithm for finding maximum matching in general
graphs. Proceedings of the 21st IEEE Symposium on Foundations of Computer Science (FOCS), pages
17–27, 1980.
[26] S. Muthukrishnan. Data streams: Algorithms and applications. Foundations and Trends in Theoretical
Computer Science, 1(2), 2005.
[27] O. Neiman and S. Solomon. Simple deterministic algorithms for fully dynamic maximal matching.
Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC), 2013.
[28] M. Zelke. Weighted matching in the semi-streaming model. Algorithmica, 62(1):1–12, 2012.

12

