## Problems

• Min-Cut $\in\text{P}$
• Max-Cut $\in\text{NPH}$
• Polynomial Identity Testing (univariate) $\in$co-$\text{NPH}$
• Input: a polynomial $f\in\mathbb{F}$ of degree $d$
• Determine whether $f\equiv0$
• PIT:
• Input: two $n$-variate polynomials $f,g\in\mathbb{F}[x_1,x_2,\cdots,x_n]$ of degree $d$
• Determine: $f\equiv g$
• Set Cover $\in\text{NPH}$:
• Input: $m$ subsets $S_1,\cdots,S_m\subseteq U$ of a universe of size $n$
• Output: $C\subseteq{1,2,\cdots, m}$ such that $U=\bigcup_{i\in C}S_i$
• $\text{freq}(x)=|{i|x\in S_i}|$
• Hitting Set Problem $\in\text{NPH}$
• Input: $n$ subsets $S_1,\cdots,S_m\subseteq U$ of a universe of size $m$
• Output $C\subseteq U$ that $C$ intersects with every set $S_i$
• $\text{freq}(x)=|S_i|$
• equivalent to Set Cover
• Vertex Cover Problem $\in\text{NPH}$
• Input: an undirect graph $G(V,E)$
• Output: the smallest $C\subseteq V$ such that $\forall e\in E$ is incident to at least one vertex in $C$
• set cover with frequency $2$
• Minimum Makespan on Identical Parallel Machine $\in\text{NPH}$
• Input: $n$ positive integers $p_1,p_2,\cdots,p_n$ nad a positive integer $m$
• Output: an assignment $\sigma:[n]\rightarrow[m]$ which minimizes $C_{\max}=\max_{i\in [m]}\sum_{j:i=\sigma(j)}p_j$
• Partition Problem $\in\text{NPH}$
• Input: $S={x_1,\cdots,x_n}$
• Output: Whether there is a partition of $S$ into $A$ and $B$ such that $\sum_{x\in A}x=\sum_{x\in B}x$
• 算法设计
• $\text{P}$: Randomize to accelerate
• $\text{NPH}$
• sampling: random approximation
• greedy/local search: approximation

## Min-Cut

### Deterministic Algorithm

• Max-flow min-cut Theory: $(|V|-1)\times$ max-flow time
• Stoer–Wagner Algorithm(multi-graphs): $O(EV+V^2\log V)$
• Ken-ichi Kawarabayashi and Mikkel Thorup(simple graph, STOC 2015): near-linear time complexity

### Karger’s Contraction Algorithm

• Contraction: merge two vertices into a new vertex
• Karger’s Algorithm(1993): $\text{ZPP}$
• Running time: $O(V^2)$
• $P_c=\frac{2}{V(V-1)}$
• w.h.p: $O(V^2\log V)$ times
RandomContract(G){
while V>2
e = choose(E)
contract(G,e)
return remaining edges
}

• Analysis Details
• Lemma: $E\geq\frac{VC}{2}$, min-cut $C$
• $p_i=1-\frac{C}{E_i}\geq 1-\frac{2}{V_i}$
• $p_{\text{correct}}\geq P_C=\prod_{i=1}^{n-2}P(e_i\not\in C|\forall j<i,e_j\not\in C)\geq \prod_{i=1}^{n-2}(1-\frac{2}{n-i+1})=\prod_{i=3}^{n}\frac{i-2}{i}=\frac{2}{n(n-1)}$

### Fast Min-Cut Algorithm

• Karger’s Algorithm improved by recursion(1996)
• Running time: $O(V^2\log V)$
• $P_c=\Omega(\frac{1}{\log V})$
• w.h.p: run $O(\log^2V)$ times
FastCut(G){
if (V<=6) return brute_force(V)
else {
t = ceil(1+V/sqrt(2))
G1 = RandomContract(G,t)
G2 = RandomContract(G,t)
return min(FastCut(G1), FastCut(G2))
}
}

• Analysis Details
• RandomContract(G,t): $P_{\text{survive}}=\frac{t(t-1)}{n(n-1)}$
• $t=\lceil 1+\frac{n}{\sqrt{2}}\rceil,P\geq \frac{1}{2}$
• $P_{\text{correct}}\geq 1-(1-\frac{1}{2}p(\lceil 1+\frac{n}{\sqrt{2}}\rceil))^2$
• $T(n)=2T(\lceil 1+\frac{n}{\sqrt{2}}\rceil)+O(n^2)$
• $T(n)=O(n^2\log_2n)$

## Max-Cut

### Greedy Heuristics

0.5-approximation algorithm

GreedyMaxCut(V,E){
S=T=emptyset
for i=1,2,...,n (random order)
vi joins one of S,T to maximize the current E(S,T)
}

• Analysis Details
• $|E|=\sum_{i=1}^n(|E(S_i,{v_i})|+|E(T_i,{v_i})|)$
• SOL$G=\sum{i=1}^n\max(|E(S_i,{v_i})|,|E(T_i,{v_i})|)\geq\frac{1}{2}E\geq\frac{1}{2}$OPT$_G$
• best known approximation ratio $\alpha^*\approx 0.878$ (best if assuming unique game conjecture)

### Derandomization from Average Case

• Randomized Algorithm: uniform and independent random bit $X_v\in{0,1}$
• $\mathbb{E}(|E(S,T)|)=\sum_{uv\in E}\mathbb{E}(I(X_u\not=X_v))=\sum_{uv\in E}P(X_u\not= X_v)=\frac{|E|}{2}\geq\frac{\text{OPT}_G}{2}$
• Probablistic method: $\exists \geq\frac{\text{OPT}_G}{2}$
• solution space: $O(2^n)$
• Derandomization by Monotone Path: $\frac{\text{OPT}G}{2}\leq\mathbb{E}(E(S,T))\leq\cdots\leq\mathbb{E}(E(S,T)|X{v_1}=x_1,\cdots,X_{v_{i-1}})\leq\cdots$
• This choice is equivalent to Greedy Heuristic one
MonotonePath(V,E){
S=T=emptyset
for i=1,2,...,n (random order)
vi joins one of S,T to maximize the average size of cut conditioning on the choices made so far by the vertice
}


### Derandomization by pairwise independence

• generate $n$ pairwise independent variables from $\log n$ mutually independent variables
• Let $X_i$ be mutually indpendent uniform random bits
• $S_i\subseteq 2^{[k]}$ be nonempty sets
• $Y_i=\oplus_{j\in S_i}X_j$, $2^k-1$ pairwise independent varibles $Y_i$
• Randomized Algorithm: $X_v$ only need to be pairwise independent
• solution space: $O(n^2)$
• exhaustive search
k = log(n)
for Y=0:2**k:
X=generatePairwise(Y)
t=assignVertexAccordingTo(X)
ans = max(ans, t)


## Coupling

• Process $G_1$ and $G_2$ share same randomness
• stochastic dominance: partial orders of random variable
• Statewise dominance: $A\geq B,\exists A>B$
• first-order stochastic dominance (FSD): $P(A\geq x)\geq P(B\geq x),\exists xP(A\geq x)>P(B\geq x)$

## Polynomial Identity Testing

• Naive Randomized Algorithm for Univariate: co-$\text{RP}$
• pick $r\in S$ and check $f(r)=0$
• false posivitve: $f\not\equiv 0,P(f(r)=0))\leq\frac{d}{|S|}$
• multivariate polymonials
• $f(x_1,\cdots,x_n)=\sum_{\sum_{j}i_j\leq d}a_{i_1,\cdots,i_n}x_1^{i_1}\cdots x_n^{i_n}$
• total degree: $i_1+\cdots+i_n$
• sum of monomials: # of coefficients ${n+d\choose d}\leq (n+d)^d$
• product form: expend is expensive but evaluate is efficient
• Randomized Algorithm
• $S\subseteq\mathbb{F}$
• pick $r_1,\cdots,r_n\in S$ uniformly and independently at random
• check $f(\overline{r})=0$
• Schwatz-Zippel Theorem: finte $\forall S\subset\mathbb{F},r_1,r_2,\cdots,r_n\in S$ choosed uniformly and independently at random, $P(f(r_1,r_2,\cdots,r_n)=0)\leq\frac{d}{|S|}$

## Set cover

• There is no poly-time algorithm with approximation ratio better than $(1-o(1))\ln n$ assuming that $\text{NP}\neq \text{P}$ (2014)

### Greedy Algorithm

• Algorithm
• Initially $C=\emptyset$
• while $U\not=\emptyset$ do
• $C=C\cup\arg\max_i|S_i\cap U|$
• $U = U\backslash S_i$
• approximation ratio $H_n\approx\ln n$
• Vertex cover problem
• $2$-approximation
• (2008) no poly-time algorithm with approximation ratio $2-\epsilon$ assuming UGC

### Primal-Dual Algorithm

• (Dual Problem) Matching: $M\subseteq U$ that $\forall i,|S_i\cap M|\leq 1$
• Find a maimal $M$, return $C={i:S_i\cap M\not=\emptyset}$
• $\max\text{freq}(x)$-approximation algorithm

## Scheduling

### Graham’s List algorithm

• List Algorithm
• for $j = 1,2,\cdots,n$: assign job $j$ to the machine that currently has the smallest load
• Approximation ratio: $2-\frac{1}{m}$
• start with a feasible solution, improve at each step by modifying locally
• start with an arbitrary schedule of $n$ jobs to $m$ machines
• while (true)
• let $\ell$ denote the job finished at last in the current schedule;
• if there is machine $i$ such that job $\ell$ can finish earlier if transferred to machine $i$
• job $\ell$ transfers to machine $i$
• else break;
• Approximation ratio: $2-\frac{1}{m}$

### Longest Processing Time (LPT)

• Algorithm
• sort $p_i$ in non-increasing order
• assign job $j$ to the machine currently has the smallest load
• Approximation: $\frac{4}{3}$
• competitive ratio: $\forall$ input sequence $I$, $\text{SOL}_I\leq\alpha\text{OPT}_I,\text{OPT}_I$ is the solution returned by optimal oofline algorithm