What is a worst case graph for this streaming algorithm?

The construction is in two steps.

First, we find a sequence of weighted graphs $G_0, G_1, G_2, \dots$ (with an ordering on their edges) where $G_n$ has the following properties:

• It has $2^{n+1}$ vertices.
• The algorithm finds a matching $M$ with a single edge $xy$ of weight $4^n$.
• There is an alternative matching $N$ with weight $(1-\varepsilon)(2\cdot 4^n - 2\cdot 2^n)$ that does not cover $x$ or $y$.

These are defined recursively. Let $G_0$ be a graph with two vertices and a single edge of weight $1$. The algorithm obviously picks that edge to be in $M$. Since $(1-\varepsilon)(2\cdot 4^0 - 2\cdot 2^0) = 0$, $N$ can be the empty matching.

Here is how we construct $G_{n+1}$, along with the order in which we present its edges to the algorithm:

1. Begin with $G_n$, presenting all its edges. After the algorithm sees all its edges, it will have $M = \{xy\}$ where $xy$ is an edge of weight $4^n$.
2. Next, add a disjoint copy of $G_n$, presenting all its edges. After the algorithm sees these edges, too, it will have $M = \{xy, x'y'\}$ where $x'y'$ is an edge in the copy of $G_{n}$ with weight $4^n$.
3. Next, present edge $yy'$, giving it weight $(1-\varepsilon)4^{n+1}$; the algorithm rejects it, because $xy$ and $x'y'$ together have weight $2 \cdot 4^n$, and so $w(e) = (1-\varepsilon)2 w(C)$.
4. Finally, present edge $xx'$, giving it weight $4^{n+1}$; the algorithm will drop $xy$ and $x'y'$ in favor of $xx'$, and output $M = \{xx'\}$ with weight $4^{n+1}$.

It remains to find the alternative matching. Let $N$ be the alternative matching in $G_n$ and let $N'$ be the alternative matching in the copy of $G_n$. Then the alternative matching in $G_{n+1}$ is $N \cup N' \cup \{yy'\}$, which does not cover $x$ or $x'$, the endpoints of the edge in $M$. Its total weight is $(1 - \varepsilon)(4^{n+1} + 4 \cdot 4^n - 4 \cdot 2^n)$ or $(1-\varepsilon)(2 \cdot 4^{n+1} - 2 \cdot 2^{n+1})$, as claimed.

To get an approximation ratio close to $\frac16$, we modify $G_n$ a bit. Let $M = \{xy\}$ be the edge found by the algorithm. We add two more vertices $x^*, y^*$ and two edges $xx^*, yy^*$ of weight $(1-\varepsilon)(2 \cdot 4^n)$ each. The algorithm will reject these, because their weight is less than twice the weight of $xy$.

However, $N \cup \{xx^*, yy^*\}$ is a matching of weight $(1-\varepsilon)(6 \cdot 4^n - 2 \cdot 2^n)$. This is $(1 - \varepsilon)(6 - \frac1{2^{n-1}})$ times the weight of $M$, so as $\varepsilon \to 0$ and $n\to \infty$, the approximation ratio can be made arbitrarily close to $\frac16$.

Here is an example of $G_3$ after this modification; the edges are given to the streaming algorithm in order of increasing weight. The algorithm will find a matching consisting only of the edge with weight $64$, but the matching consisting only of edges whose weight ends in $.99$ is much better: it has weight $367.91$ (almost $368$), so the approximation ratio is a tiny bit better than $\frac{64}{368} = \frac{4}{23}$. (This is not quite $\frac16 = \frac{4}{24}$, because $n=3$ is still far from $n\to\infty$.)