# Algorithm - Homework 3

姓名: 陈声发
学号：2019280355

## Problem 1


We can maintain winning statistics of player 0 and a play terminates with a win for player 0 iff player 0 is declared a winner and the play is a win for player 1 iff it runs forever.

The set Q of nodes of this game consists of nodes of the form $(a, p, \tilde{b})$ where $a$ is a node of the parity game, the player $p \in \{\text{player 0}, \text{player 1}\}$ moves next and $\tilde{b}$ represents the winning statistics of player 0.

The number of elements of Q can be bounded by $O(n^4)$.

The starting node is $(s, p, \tilde 0)$, where $\tilde 0$ is the vector of all $b_i$ with value 0, $s$ is the starting
node of the parity game and $p$ is the player who moves first.

Note that the number of increasing functions from $\{0, 1, 2, . . . , log(n) + 2\}$ to $\{1, 2, 3, . . . , \log(n)\}$ can be bounded by $O(n^2)$.

And $b^\prime_k\leq b^\prime_{k+1}$ implies $b^\prime_k + k \lt b^\prime_{k+1}+k+1$ and therefore the set can construct all the $b^\prime_k$. So we need at most $\log n+3$ additional bits to indicate which $b_k$ is 0. The overall winning statistics can then be represented by $3\log n + 5$ bits. And we need 1 bit to represent the player and $\log n$ bits to represent the current node in the play. So each node can be represented with $4 \log n$ + 6 bits resulting in $O(n^4)$ node in $Q$.

Therefore, the time complexity is $O(2^m n^4)$, where m is the number of distinct value on the nodes.
For $m \leq \log n$, there is a solution of time complexity $O(n^5)$.

<div style="page-break-after: always;"></div>

## Problem 2


We know all matching edges are tight and every blossom $B$ contains $\frac{|B|-1}{2}$ matching edges
+ $w(M^*)=\sum_{e\in M^*}yz(e)=\sum_{u\in V}y(u)+\sum_{b\in\Omega}z(B)\frac{|B|-1}{2}$

For every other matching $M$, a blossom $B$ contains no more than $\frac{|B|-1}{2}$ edges of $M$
+ $w(M)$
$\leq\sum_{e\in M}yz(e)$
$=\sum_{u\in V}y(u)+\sum_{b\in\Omega}z(B)|M\cap E(B)|$
$\leq\sum_{u\in V}y(u)+\sum_{b\in\Omega}z(B)\frac{|B|-1}{2}$

Therefore, $M^*$ is a maximum weighted matching.

<div style="page-break-after: always;"></div>

## Problem 3

There are at most $O(\frac{m}{t})$ dense rows or columns.
The multiplication of dense part taks $n^{ω(p)}=O(\max\{n^2,n^2(\frac{m}{tn^α})^β\})$ time.
The naive multiplication enumerates at most $O(t)$ many nonzero $b_{j,k}$ for each nonzero $a_{i,j}$, so it takes $O(mt)$ time.
In total $O(\max\{n^2,n^2(\frac{m}{tn^α})^β\}+mt)$ time.
We choose $t=O(\frac{n^{\frac{2-αβ}{1+β}}}{m^{\frac{1-β}{1+β}}})$, time complexity $O(\max\{n^2,n^{\frac{2-αβ}{1+β}}m^{\frac{2β}{1+β}}\})$.
Let $m=n^k$, the time complexity has a better bound than $O(n^ω)$ when $m<n^{\frac{α+ω}{2}+\frac{ω-2}{2β}}$.