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_k^{\prime }\le b_{k+1}^{\prime }$ implies

$b_k^{\prime }+k<b_{k+1}^{\prime }+k+1$ and therefore the set can construct all the

$b_k^{\prime }$. 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\le \log n$, there is a solution of time complexity

$O(n^5)$.

Problem 2

We know all matching edges are tight and every blossom

$B$ contains

$\frac{|B|-1}{2}$ matching edges

• $w(M^{\ast })=\sum _{e\in M^{\ast }}yz(e)=\sum _{u\in V}y(u)+\sum _{b\in \mathrm{\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)$
  
  $\le \sum _{e\in M}yz(e)$
  
  $=\sum _{u\in V}y(u)+\sum _{b\in \mathrm{\Omega }}z(B)|M\cap E(B)|$
  
  $\le \sum _{u\in V}y(u)+\sum _{b\in \mathrm{\Omega }}z(B)\frac{|B|-1}{2}$

Therefore,

$M^{\ast }$ is a maximum weighted matching.

Problem 3

There are at most

$O(\frac{m}{t})$ dense rows or columns.
The multiplication of dense part taks

$n^{\omega (p)}=O(max\{n^2,n^2(\frac{m}{t{n}^{\alpha }}{)}^{\beta }\})$ 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}{t{n}^{\alpha }}{)}^{\beta }\}+mt)$ time.
We choose

$t=O(\frac{n^{\frac{2-\alpha \beta }{1+\beta }}}{m^{\frac{1-\beta }{1+\beta }}})$, time complexity

$O(max\{n^2,n^{\frac{2-\alpha \beta }{1+\beta }}{m}^{\frac{2\beta }{1+\beta }}\})$.
Let

$m=n^k$, the time complexity has a better bound than

$O(n^{\omega })$ when

$m<n^{\frac{\alpha +\omega }{2}+\frac{\omega -2}{2\beta }}$.