# Lecture 10 - General Matchings and Market Equilibriums

###### tags: `Algorithm`

## General Matchings
### LP and Dual problem
+ Linear Program for matching in general graph

| $\max\sum_{e\in E}w(e)x(e)$ |
| --- |
|s.t. $$0\leq x(e)\leq 1,e\in E\\\sum_{e=(u,u')\in E}x(e)\leq 1, u\in V\\ x(e)\in\Bbb N, e\in E$$ |
+ $x(e)\in\Bbb N, e\in E$ cannot be removed
+ Odd set constrain $$\sum_{e=(u,v)\\u,v\in B}x(e)\leq (|B|-1)/2,\forall B\subseteq V, |B|\in odd$$

+ Dual for general matching

| $\min\sum_{u\in V(G)}y(u)+\sum_{B\in V_{odd}}\frac{\vert B \vert -1}{2}z(B)$ |
| --- |
| s.t. $$yz(e)\geq w(e),\forall e\in E(G)\\y(u)\geq 0,z(B)\geq 0,\forall u\in V(G),\forall B\in V_{odd}$$ where $$yz(u,v)=y(u)+y(v)+\sum_{B\in V_{odd}\\(u,v)\in E(B)}z(B)$$|

+ $B$ is a **blossom**
+ A **blossom** $B$ is a cycle in $G$ consisting of $2k+1$ edges of which exactly $k$ are matching edges

### Blossom
+ A **blossom** $B$ is a cycle in $G$ consisting of $2k+1$ edges of which exactly $k$ belong to $M$
+ The only vertex whose matching edge is not in $B$ is called the **base**
#### Property
+ Edges associated with any vertex in the blossom can be in an augmenting path
#### Shrinking the Blossom
+ Thus in the search blossoms can be shrunk to one vertex, we call it contracted graph
+ Then we find augmenting paths in the contracted graph
+ Finally we can unshrink the graph and get the real augmenting paths
+ A blossom can contain other smaller blossoms

### Solution: Dual-variables on Blossoms
+ *Edmond*’s primal-dual algorithm
+ $y:V\to\Bbb R$
+ $z:B\to\Bbb R,z\geq 0$
+ $yz(u,v)=y(u)+y(v)+\sum_{u,v\in B}z(B)$
+ They will satisfy
+ $z(B)\geq 0$ for all blossoms $B$, and $z(B)>0$ if $B$ is a root blossom
+ $yz(e)\geq w(e)$ for all edges $e$
+ $yz(e)=w(e)$ if $e$ is a matching edge or a **blossom edge**
+ So all blossom edges are tight
#### Why we need $z$ value
+ Remind the difficulty: 
+ Now we can just minus (plus) $Δ$ to all the vertices in the blossom, and plus (minus) $2Δ$ to the $z$-value of the root blossom
+ Then $yz(e)$ for edges in the blossom will remain unchange
### *Edmond*'s Algorithm
+ Eligible edges
+ Matching edges
+ Blossom edges
+ Other edges satifying $yz(e)=w(e)$
+ Search from all free vertices
+ We mark the vertices OUT and IN, based on their lengths of alternating path to free vertices (EVEN or ODD)
+ There is contracted graph $G’$ which contracts all blossoms
+ Run breath-first search from all free vertices on eligible edges
+ If we find an edge connecting OUT vertices, there is an augmenting path or a new blossom
+ An augmenting path: update the matching M, blossoms and $G'$
+ New blossom: Shrinking the blossom $B$, $z(B):=0$, update $G'$
+ Otherwise run the dual-adjustment
+ For vertex $v’$ in $G’$ which have been labeled OUT or IN, we labeled OUT or IN to the original vertex $v$ in $G$ contained in $v’$
+ $y(v):=y(v)-Δ$ for all OUT vertex v
+ $y(v):=y(v)+Δ$ for all IN vertex v
+ $z(B):=z(B)+2Δ$ if $B$ is a root blossom containing OUT vertices
+ $z(B):=z(B)-2Δ$ if $B$ is a root blossom containing IN vertices
+ Dissolve root blossoms with zero $z$-values (non-root blossoms can have zero $z$-values), update $G’$ and set of eligible edge
#### Augmentation
+ Since a blossom can have positive $z$-value, we cannot dissolve all the blossoms
+ On the augmenting path, switch between non-matching and matching in $G’$ and in every blossom
+ So for every blossom on the augmenting path, the base will change
+ After augmentation, functions $y,z$ and blossoms do not change, so all tight edges (including all matching edges and blossom edges) remain tight
+ We need to dissolve all root blossoms of zero $z$-value
## Combinatorial Algorithm for Linear Markets